﻿#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <math.h> 
#include <iomanip>
#include <fstream>
#include <bitset>
#include <sstream>    
using namespace std;
//#define M_PI (ldb)3.14159265358979323846 // pi 
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define forrb(i,a,b,c) for(int i=a;i>b;i-=c)
#define fori(i,n) forr(i,0,n,1)
#define forit(it,arr) for(auto it=arr.begin();it != arr.end();it++)
#define forib(i,n) forrb(i,n-1,-1,1)
#define forn(i,n) forr(i,1,n,1)
#define fornb(i,n) forrb(i,n-1,0,1)
#define fort(i,m,n) forr(i,m,n,1)
#define fortb(i,m,n) forrb(i,n-1,m-1,1)
#define forin(i,arr) fori(i,arr.size())
#define forinb(i,arr) forib(i,arr.size())
#define forrl(i,a,b,c) for(lol i=a;i<b;i+=c)
#define forrbl(i,a,b,c) for(lol i=a;i>b;i-=c)
#define foril(i,n) forrl(i,0,n,1)
#define foribl(i,n) forrbl(i,n-1,-1,1)
#define fornl(i,n) forrl(i,1,n,1)
#define fornbl(i,n) forrbl(i,n-1,0,1)
#define fortl(i,m,n) forrl(i,m,n,1)
#define fortbl(i,m,n) forrbl(i,n-1,m-1,1)
#define forinl(i,arr) foril(i,arr.size())
#define forinbl(i,arr) foribl(i,arr.size())
#define forpm(i) forr(i,-1,2,2)
#define into(i) cin >> i;
#define intov(arr,n) fori(kkkk,n){into(arr[kkkk])}
#define def(i) lol i; into(i)
#define deft(t,i) t i; into(i)
#define defl(i) lol i; into(i)
#define defs(i) string i; into(i)
#define defn def(n)
#define defp def(p)
#define defm def(m)
#define defk def(k)
#define defa def(a)
#define defb def(b)
#define defc def(c)
#define defd def(d)
//#define vec(a) vector<a>
#define co cout <<
#define out(a) cout << (a) <<' ';
#define el << endl;
#define ell << '\n';
#define outv(arr,n) fori(iii,n){out(arr[iii])} co "" el
#define outvv(arr,n,m) fori(jjj,n){outv(arr[jjj],m)}
#define cas(p) co "Case #" << p+1 <<": ";
#define ex return 0; 
#define qii queue<int>
#define sti stack<int>
#define dei deque<int>
#define seti set<int>
#define con continue;
#define br break;
#define maxi 1000000007
// 998244353
#define maxiu 4294967295
#define lmaxi 2000000000000000007
#define mod %maxi
#define wne(arr) while(!arr.empty())
#define all(arr) arr.begin(),arr.end()
#define getv(arr,n) fori(i,n) {into(arr[i])}
#define defv(arr,n) veci arr(n); fori(i,n) {into(arr[i])}
#define min2(a,b) a=min(a,b);
#define max2(a,b) a=max(a,b);
#define vec vector
#define ff first
#define ss second
#define pow2(x) (x)*(x)
#define pow3(x) (x)*(x)*(x)
#define getgraph(m,cons) fori(i,m){defa defb a--; b--; cons[a].push_back(b);cons[b].push_back(a);}
#define getdirectedgraph(m,cons) fori(i,m){defa defb a--; b--; cons[a].push_back(b);}
#define getwightedgraph(m,cons) fori(i,m){defa defb defc a--; b--; cons[a].push_back({b,c});cons[b].push_back({a,c});}
#define getwighteddirectedgraph(m,cons) fori(i,m){defa defb defc a--; b--; cons[a].push_back({b,c});}
typedef vector<int> veci;
typedef long long lol;
typedef unsigned long long ulol;
typedef unsigned int uint;
typedef long double ldb;
typedef vector<lol> vecl;
typedef vector<uint> vecui;
typedef vector<ulol> vecul;
#define table(name,n,m) vector<veci> name(n,veci (m));
#define tablel(name,n,m) vector<vecl> name(n,vecl (m));
typedef pair<lol, lol> point;
#define setp set<point>
#define bmod %99999999999899999
typedef pair<point, point> poin;
typedef pair<long double, long double> pointd;
typedef pair<lol, point> poing;
typedef pair<point, lol> poinf;
typedef vector<point> vecp;
#define poi(x,y) make_pair(x,y)
struct BigNum {
#define sizer (lol) 1e9
#define digss (lol) 9
	vecl value;
	void set(lol x) { value = *(new vecl); value.push_back(x); }
	void duplicate(BigNum other) { value = other.value; }
	void add(BigNum other) {
		vecl o = other.value;
		if (o.size() > value.size()) {
			vecl t = value;
			value = o;
			o = t;
		}
		forin(i, o) {
			value[i] += o[i];
			if (i < value.size() - 1 && value[i] >= sizer) {
				value[i + 1] += value[i] / sizer;
				value[i] = value[i] % sizer;
			}
		}
		if (value.back() >= sizer) {
			value.push_back(value.back() / sizer);
			value[value.size() - 2] = value[value.size() - 2] % sizer;
		}
	}
	void mul(lol mul) {
		forin(i, value) {
			value[i] *= mul;
		}
		fori(i, value.size() - 1) {
			if (value[i] >= sizer) {
				value[i + 1] += value[i] / sizer;
				value[i] = value[i] % sizer;
			}
		}
		if (value.back() >= sizer) {
			value.push_back(value.back() / sizer);
			value[value.size() - 2] = value[value.size() - 2] % sizer;
		}
	}
	long double div(BigNum other1, BigNum other2) {
		int s = value.size();
		long double current = value.back();
		if (s >= 2) {
			current += ((long double)value[s - 2]) / sizer;
		}
		if (s >= 3) {
			current += ((long double)value[s - 3]) / (sizer * sizer);
		}
		int s1 = other1.value.size();
		int s2 = other2.value.size();
		long double other = 0;
		if (s1 + s2 - 1 == s) {
			other += other1.value.back() * other2.value.back();
			if (s1 >= 2) {
				other += ((long double)other1.value[s1 - 2] * other2.value.back()) / sizer;
			}
			if (s2 >= 2) {
				other += ((long double)other2.value[s2 - 2] * other1.value.back()) / sizer;
			}
			if (s1 >= 3) {
				other += ((long double)other1.value[s1 - 3] * other2.value.back()) / (sizer * sizer);
			}
			if (s2 >= 3) {
				other += ((long double)other2.value[s2 - 3] * other1.value.back()) / (sizer * sizer);
			}
		}
		if (s1 + s2 - 1 == s - 1) {
			other += other1.value.back() * other2.value.back();
			if (s1 >= 2) {
				other += ((long double)other1.value[s1 - 2] * other2.value.back()) / sizer;
			}
			if (s2 >= 2) {
				other += ((long double)other2.value[s2 - 2] * other1.value.back()) / sizer;
			}
			other /= sizer;
		}
		if (s1 + s2 - 1 == s - 2) {
			other += other1.value.back() * other2.value.back();
			other /= sizer * sizer;
		}
		return other / current;
	}
	string stringify() {
		string out = to_string(value.back());
		forib(i, value.size() - 1) {
			string cur = to_string(value[i] + sizer);
			out += cur.substr(1);
		}
		return out;
	}
};
lol gcd(lol a, lol b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
lol triangle(lol x) {
	return ((x - 1) * x) / 2;
}
lol antitriangle(lol x) {
	lol low = 0, high = 2 * maxi;
	while (low < high) {
		lol mid = (low + high + 1) / 2;
		if (triangle(mid) <= x) {
			low = mid;
		}
		else {
			high = mid - 1;
		}
	}
	return low;
}
lol modInverse(lol a)
{
	lol m = maxi;
	lol y = 0, x = 1;
	while (a > 1)
	{
		lol q = a / m;
		lol t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += maxi;
	}
	return x;
}
lol modInverse(lol a, lol b)
{
	lol m = b;
	lol y = 0, x = 1;
	while (a > 1)
	{
		lol q = a / m;
		lol t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += b;
	}
	return x;
}
lol poww(lol a, lol b) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 0) {
		return poww((a * a)mod, b / 2)mod;
	}
	return (a * poww((a * a)mod, b / 2))mod;
}
lol pow(lol a, lol b, lol m) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 0) {
		return pow((a * a) % m, b / 2, m) % m;
	}
	return (a * pow((a * a) % m, b / 2, m)) % m;
}
vecl dev(vecp divisors) {
	if (divisors.size() == 0) {
		vecl cur;
		cur.push_back(1);
		return cur;
	}
	lol x = divisors.back().first;
	lol n = divisors.back().second;
	divisors.pop_back();
	vecl ans = dev(divisors);
	vecl cur;
	lol xi = 1;
	fori(i, n + 1) {
		forin(j, ans) {
			cur.push_back(ans[j] * xi);
		}
		xi *= x;
	}
	return cur;
}
bool isprime(lol a) {
	if (a == 1) {
		return false;
	}
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			return false;
		}
	}
	return true;
}
void add(veci & x, veci & y) {
	forin(i, x) {
		x[i] += y[i];
	}
}
vecl mul(vecl x, lol a) {
	forin(i, x) {
		x[i] = (x[i] * a)mod;
	}
	return x;
}
vecl add(vecl x, vecl & y) {
	forin(i, x) {
		x[i] = (x[i] + y[i])mod;
	}
	return x;
}
#define logn 18
int lca(vector<veci> & f, veci & depth, int a, int b) {
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	fori(k, logn) {
		if ((depth[a] - depth[b]) & (1 << k)) {
			a = f[k][a];
		}
	}
	if (a == b) {
		return a;
	}
	forib(k, logn) {
		if (f[k][a] != f[k][b]) {
			a = f[k][a];
			b = f[k][b];
		}
	}
	return f[0][a];
}
int tredist(vector<veci>& f, veci& depth, int a, int b) {
	return depth[a]+ depth[b]- 2*depth[lca(f,depth,a,b)];
}
struct pt
{
#define intopt(a) into(a.x) into(a.y)
#define defpt(a) pt a;intopt(a)
	lol x, y;
	lol d() const // squared length
	{
		return x * x + y * y;
	}
};
typedef vector<pt> vecpp;
inline pt operator-(const pt & a) { return { -a.x, -a.y }; }
inline pt operator+(const pt & a, const pt & b) { return { a.x + b.x, a.y + b.y }; }
inline pt operator-(const pt & a, const pt & b) { return { a.x - b.x, a.y - b.y }; }
inline lol operator*(const pt & a, const pt & b) { return a.x* b.y - a.y * b.x; } // cross product
inline bool operator<(const pt& a, const pt& b) { if (a * b != 0) return a * b < 0; return a.d() < b.d(); }
bool llll(const pt & a, const pt & b) { return a * b > 0; }
inline bool operator<=(const pt & a, const pt & b) { return a * b <= 0; }
inline lol operator/(const pt & a, const pt & b) { return a.x* b.x + a.y * b.y; } // dot product
inline bool operator==(const pt & a, const pt & b) { return a.x == b.x && a.y == b.y; } // equal
inline bool operator!=(const pt & a, const pt & b) { return a.x != b.x || a.y != b.y; } // not equal
pt o = { 0 ,0 };
bool comp(pt a, pt b) {
	if ((a - o) * (b - o) != 0)
		return (a - o) * (b - o) < 0;
	return (a - o).d() < (b - o).d();
}
bool decreasing(int a, int b) {
	return a > b;
}
#define digits 30
struct booleantree
{
	booleantree* left = NULL;
	booleantree* right = NULL;
	void add(int val) {
		booleantree* cur = this;
		forib(i, digits) {
			if ((val & (1 << i))) {
				if (cur->right == NULL) {
					cur->right = new booleantree();
				}
				cur = cur->right;
			}
			else {
				if (cur->left == NULL) {
					cur->left = new booleantree();
				}
				cur = cur->left;
			}
		}
	}
	int find(int val) {
		booleantree* cur = this;
		int ans = 0;
		forib(i, digits) {
			if ((val & (1 << i))) {
				if (cur->left == NULL) {
					cur = cur->right;
				}
				else {
					cur = cur->left;
					ans += (1 << i);
				}
			}
			else {
				if (cur->right == NULL) {
					cur = cur->left;
				}
				else {
					cur = cur->right;
					ans += (1 << i);
				}
			}
		}
		return ans;
	}
};
struct segtremin {
	vector<vecl> arr;
	int n;
	int curlogn;
	segtremin(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
	}
	inline lol val(int start, int end) {
		if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}
		lol mini = lmaxi;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				min2(mini, arr[i][end]);
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				min2(mini, arr[i][start])
					start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = min(arr[i - 1][(start >> i) * 2], arr[i - 1][(start >> i) * 2 + 1]);
		}
	}
};
struct segtreminplus {
	vecl arr;
	vector<vecl> arr2;
	vector<vecl> arr3;
	vector<vecl> arr4;
	int n;
	int curlogn;
	segtreminplus(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(size + 1);
		arr2.resize(curlogn);
		fori(i, curlogn) {
			arr2[i].resize(size + 1);
		}
		arr3.resize(curlogn);
		fori(i, curlogn) {
			arr3[i].resize(size + 1);
		}
		arr4.resize(curlogn);
		fori(i, curlogn) {
			arr4[i].resize(size + 1);
		}
	}
	inline void fixcate(int i, int j) {
		if (j < 0) {
			return;
		}
		if (i == 0) {
			arr2[i][j] = 1;
			arr3[i][j] = 1;
			arr4[i][j] = 1;
			return;
		}
		arr2[i][j] = max(arr2[i-1][2*j], arr2[i - 1][2 * j+1]);
		arr3[i][j] = arr3[i - 1][2 * j];
		arr4[i][j] = arr4[i - 1][2 * j+1];
		if (((2 * j + 1) << (i - 1)) < n && arr[((2 * j + 1) << (i - 1))] > arr[((2 * j + 1) << (i - 1)) - 1]) {
			arr2[i][j] = max(arr2[i][j], arr4[i - 1][2 * j]+ arr3[i - 1][2 * j+1]);
			if (arr2[i - 1][2 * j+1] == (1 << (i - 1))) {
				arr4[i][j] = arr4[i - 1][2 * j + 1] + arr4[i - 1][2 * j];
			}
			if (arr2[i - 1][2 * j] == (1 << (i - 1))) {
				arr3[i][j] = arr3[i - 1][2 * j + 1] + arr3[i - 1][2 * j];
			}
		}
	}
	inline lol val(int start) {
		if (start > 0) {
			return arr[start];
		}
		return arr2[curlogn-1][0];
	}
	inline void change(int start, lol num) {
		arr[start] = num;
		fori(i, curlogn) {
			fixcate(i, start >> i);
		}
	}
};
struct segtresum {
	vector<vecl> arr;
	int n;
	int curlogn;
	segtresum(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
	}
	inline lol val(int start, int end) {
		/*if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}*/
		lol mini = 0;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				mini += arr[i][end];
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				mini += arr[i][start];
				start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
	inline void radd(int start, lol num) {
		arr[0][start] += num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
};
struct segtresumplus {
	vector<vecl> arr;
	vector<vecl> arrplus;
	vector<vecl> truearrplus;
	int n;
	int curlogn;
	segtresumplus(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
		arrplus.resize(curlogn);
		fori(i, curlogn) {
			arrplus[i].resize(size + 1);
		}
		truearrplus.resize(curlogn);
		fori(i, curlogn) {
			truearrplus[i].resize(size + 1);
		}
	}
	inline void fix(int h, int s) {
		/*if (arrplus[h][s] == 0) {
			return;
		}
		arr[h][s] += arrplus[h][s] << h;
		if (h > 0) {
			arrplus[h - 1][2 * s] += arrplus[h][s];
			arrplus[h - 1][2 * s+ 1] += arrplus[h][s];
		}
		arrplus[h][s] = 0;*/
	}
	inline lol val(int start, int end) {
		/*if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}*/
		forib(i, curlogn) {
			fix(i, start >> i);
			fix(i, end >> i);
		}
		lol mini = 0;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				fix(i, end);
				mini += arr[i][end];
				mini += arrplus[i][end];
				fort(j, i + 1, curlogn) {
					mini += truearrplus[j][end >> (j-i)]<< i;
				}
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				fix(i, start);
				mini += arr[i][start];
				mini += arrplus[i][start];
				fort(j, i + 1, curlogn) {
					mini += truearrplus[j][start >> (j - i)] << i;
				}
				start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
	inline void radd(int start,int end, lol num) {
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				truearrplus[i][end]+=num;
				fort(j,i, curlogn) {
					arrplus[j][end >> (j-i)] += num << i;
				}
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				truearrplus[i][start] += num;
				fort(j, i, curlogn) {
					arrplus[j][start >> (j - i)] += num << i;
				}
				start++;
			}
			start /= 2;
			end /= 2;
		}
	}
};
struct unionfind{
	veci arr;
veci arr2;
int num;
unionfind(int size) {
	arr.resize(size);
	arr2.resize(size);
	num = size;
	fori(i, size) {
		arr[i] = i;
		arr2[i] = 1;
	}
}
int find(int a) {
	if (arr[a] == a) {
		return a;
	}
	return arr[a] = find(arr[a]);
}
inline void unioner(int a, int b) {
	a = find(a), b = find(b);
	if (a != b) {
		num--;
		if (arr2[a] > arr2[b]) {
			swap(a, b);
		}
		arr[a] = b;
		arr2[b] += arr2[a];
	}
}
};
string op(string s) {
	string ans;
	forinb(i, s) {
		ans.push_back(s[i]);
	}
	return ans;
}
void merge(veci& color, vector<veci>& allcolor, int l, int r) {
	if (color[l] == color[r]) {
		return;
	}
	l = color[l];
	r = color[r];
	if (allcolor[l].size() < allcolor[r].size()) {
		swap(l, r);
	}
	forin(j, allcolor[r]) {
		color[allcolor[r][j]] = l;
		allcolor[l].push_back(allcolor[r][j]);
	}
	allcolor[r].resize(0);
}
vecpp conv(vecpp a) {
	pt left = { 99999999999999,999999999999999 };
	forin(i, a) {
		if (a[i].x < left.x || a[i].x == left.x && a[i].y > left.y) {
			left = a[i];
		}
	}
	o = left;
	forin(i, a) {
		if (a[i] == left) {
			a[i] = a.back();
			a.pop_back();
			br
		}
	}
	sort(all(a), comp);
	vecpp conv(1, left);
	forin(i, a) {
		while (conv.size() > 1) {
			if ((a[i] - conv.back()) * (conv.back() - conv[conv.size() - 2]) <= 0) {
				conv.pop_back();
			}
			else {
				br
			}
		}
		conv.push_back(a[i]);
	}
	while (conv.size() > 1) {
		if ((left - conv.back()) * (conv.back() - conv[conv.size() - 2]) <= 0) {
			conv.pop_back();
		}
		else {
			br
		}
	}
	return conv;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	defn defm
		veci a(n);
	intov(a,n)
	vector<veci> primer(100000);
	vector<veci> nekt(logn, veci(n+1, n));
	fori(i, n) {
		fort(j,2, 400) {
			if (a[i] % j == 0) {
				primer[j].push_back(i);
				while (a[i] % j == 0) {
					a[i] /= j;
				}
			}
		}
		if (a[i] > 1) {
			primer[a[i]].push_back(i);
		}
	}
	forin(i, primer) {
		fori(j, ((int)primer[i].size())-1) {
			min2(nekt[0][primer[i][j]], primer[i][j + 1]);
		}
	}
	forib(i, n-1) {
		min2(nekt[0][i], nekt[0][i+1]);
		forn(j, logn) {
			nekt[j][i] = nekt[j - 1][nekt[j - 1][i]];
		}
	}
	fori(i, m) {
		defa defb
			int ans = 1;
		a--;
		int k = logn - 1;
		while (k >= 0) {
			if (nekt[k][a] < b) {
				a = nekt[k][a];
				ans += 1 << k;
			}
			else {
				k--;
			}
		}
		co ans el
	}
	ex
}