#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	int n,q; cin>>n>>q;
	vector<int> a(n);
	for (int& x: a) cin>>x;
	vector<array<int,3>> qs;
	for (int i=0; i<q; i++) {
		int l,r; cin>>l>>r, l--, r--;
		qs.push_back({l,r,i});
	}
	
	vector<vector<int>> isd(*max_element(a.begin(), a.end())+1);
	for (int i=0; i<n; i++) {
		isd[a[i]].push_back(i);
		for (int j=2; j*j<=a[i]; j++) {
			if (a[i]%j==0) {
				isd[j].push_back(i);
				if (j*j!=a[i]) isd[a[i]/j].push_back(i);
			}
		}
	}

	vector<vector<array<int,2>>> endpts(n);
	for (int i=2; i<isd.size(); i++) {
		int r=0;
		for (int l=0; l+1<isd[i].size(); l++) {
			int cur=isd[i][l], nxt=isd[i][l+1];
			while (r<isd[i].size() && nxt-cur > isd[i][r]-nxt) r++;
			if (r==isd[i].size()) break;
			endpts[cur].push_back({isd[i][r], i});
		}
	}

	sort(qs.begin(), qs.end(), greater<array<int,3>>());
	map<int, int> m;
	int cl=n-1;
	vector<int> ans(q, 0);
	for (auto [l,r,qi]: qs) {
		if (r-l<=1) continue;

		for (; l<=cl; cl--) {
			for (auto [right, val]: endpts[cl]) {
				auto it = m.upper_bound(right);
				if (it!=m.begin() && prev(it)->second >= val) continue;
				it = next(m.insert_or_assign(right, val).first);
				while (it!=m.end() && it->second<=val) it=m.erase(it);
			}
		}

		auto it = m.upper_bound(r);
		if (it==m.begin()) ans[qi]=1;
		else ans[qi]=prev(it)->second;
	}

	for (int v: ans) cout<<v<<"\n";
}