#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++) 
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--) 
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int N = 1e6 + 47;
const int N2 = 2e7 + 47;

struct Query
{
	int l, r, val;
	
	bool operator<(const Query& q)
	{
		if (l != q.l)
			return l > q.l;
		return val > q.val;
	}
	
};

VI idx[N];
Query qe[N2];
int qh = 0;

struct Fenwick
{
	int n;
	VI t;
	
	Fenwick(int _n = 0): n(_n), t(n, 1) {}
	
	void upd(int i, int x)
	{
		for (; i < n; i |= i + 1)
			t[i] = max(t[i], x);
	}
	int query(int i)
	{
		int ans = 1;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans = max(ans, t[i]);
		return ans;
	}
};


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	VI a(n);
	FOR (i, 0, n)
	{
		cin >> a[i];
		idx[a[i]].PB(i);
	}
	int mx = *max_element(ALL(a));
	FOR (d, 2, mx + 1)
	{
		VI poses;
		for (int j = d; j <= mx; j += d)
			poses.insert(poses.end(), ALL(idx[j]));
		sort(ALL(poses));
		FOR (i, 1, SZ(poses))
		{
			int dis = poses[i] - poses[i - 1];
			int j = lower_bound(ALL(poses), poses[i] + dis) - poses.begin();
			if (j != SZ(poses))
			{
				if (gcd(a[poses[i - 1]], gcd(a[poses[i]], a[poses[j]])) == d)
					qe[qh++] = {poses[i - 1], poses[j], d};
			}
		}
	}
	FOR (i, 0, q)
	{
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (r - l > 1)
			qe[qh++] = {l, r, -i - 1};
	}
	sort(qe, qe + qh);
	Fenwick fn(n);
	VI ans(q);
	FOR (i, 0, qh)
	{
		int r = qe[i].r;
		int val = qe[i].val;
		//cerr << i << ' ' << r << ' ' << val << '\n';
		if (val > 0)
			fn.upd(r, val);
		else
			ans[-val - 1] = fn.query(r);
	}
	FOR (i, 0, q)
	{
		cout << ans[i] << '\n';
	}
	
	return 0;
}