#include<bits/stdc++.h>
// #define int long long
#define eb emplace_back
#define mp make_pair
// #define DEBUG
using namespace std;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using piiii = pair<pii, pii>;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int P = 998244353;const i64 inf = 0x3f3f3f3f3f3f3f3f;
namespace BIT{
	#define lowbit(u) (u & -u)
	int add(vector<int> &tr, int u, int v){
		int n = tr.size() - 1;
		u ++;
		for(; u <= n; u += lowbit(u))
			tr[u] = max(tr[u], v);
		return 0;
	}
	int ask(vector<int> &tr, int u){
		int ret = 0;
		u ++;
		for(; u; u -= lowbit(u)){
			ret = max(ret, tr[u]);
		}
		return ret;
	}
} using namespace BIT;
namespace azus{
	int n, q;
	vector<int> pos[1000005];
	vector<int> fac[1000005];
	vector<pii> cq[200005];
	unordered_set<int> s[200005];
	vector<int> tr;
	vector<pii> que[200005];
	int ans[200005];
	int main(){
		cin >> n >> q;
		for(int i = 1; i <= n; i ++){
			int x; cin >> x; pos[x].eb(i);
		}
		for(int i = 1; i <= 1000000; i ++){
			for(int j = i; j <= 1000000; j += i){
				for(int k : pos[j])
					fac[i].eb(k);
			}
			sort(fac[i].begin(), fac[i].end());
		}
		for(int i = 1000000; i >= 1; i --){
			if(fac[i].size() < 3) continue;
			int w = fac[i].size();
			int r = 2;
			for(int l = 0; l < w - 1; l ++){
				int m = l + 1;
				int len = fac[i][m] - fac[i][l];
				int cw = fac[i][m] + len;
				while(fac[i][r] < cw && r < w) r ++;
				if(r == w) break;
				if(s[fac[i][r]].find(l) != s[fac[i][r]].end()){
					continue;
				}
				s[fac[i][r]].insert(fac[i][l]);
				cq[fac[i][r]].eb(mp(fac[i][l], i));
			}
		}
		tr.assign(n + 5, 0);
		for(int i = 1; i <= q; i ++){
			int l, r; cin >> l >> r;
			que[r].eb(mp(l, i));
		}
		for(int i = 1; i <= n; i ++){
			for(auto [l, vl] : cq[i]){
				add(tr, (n - l + 1), vl);
			}
			for(auto [l, id] : que[i]){
				ans[id] = ask(tr, n - l + 1);
			}
		}
		for(int i = 1; i <= q; i ++){
			cout << ans[i] << "\n";
		}
		return 0;
	}
}
signed main(){
#ifndef DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#endif
	int T = 1;
	while(T --)
		azus::main();
	return 0;
}