#include<bits/stdc++.h>
using namespace std;
const int N = 5e7 + 10, M = 1e4 + 10;
int n, q, len, cnt;
int a[N], w[N], sum[M];
vector<int> factor[N];
struct Node
{
    int op, l, r, d, id;
}segment[N];

bool cmp1(Node x, Node y)
{
    if (x.l == y.l) return x.op < y.op;
    return x.l < y.l;
}

bool cmp2(Node x, Node y)
{
    if (x.op == y.op) return x.id < y.id;
    return x.op < y.op;
}

int get(int x)
{
    return (x - 1) / len;
}

int query(int l, int r)
{
    int res = 0;
    if (get(l) == get(r))
        for (int i = l; i <= r; i ++ )
            res = max(res, w[i]);
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) res = max(res, w[i]), i ++ ;
        while (get(j) == get(r)) res = max(res, w[j]), j -- ;
        for (i = get(i); i <= get(j); i ++ ) res = max(res, sum[i]);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    int maxx = 0;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], maxx = max(maxx, a[i]);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j * j <= a[i]; j ++ )
            if (a[i] % j == 0)
                if (j * j != a[i]) factor[j].push_back(i), factor[a[i] / j].push_back(i);
                else factor[j].push_back(i);
    for (int i = 1; i <= q; i ++ )
    {
        int l, r;
        cin >> l >> r;
        segment[ ++ cnt] = {0, l, r, 0, i};
    }
    for (int i = 1; i <= maxx; i ++ )
    {
        int last = factor[i].size();
        for (int l = last - 3, r = last - 1; l >= 0; r -- )
        {
            while (l >= 0 && factor[i][r] - factor[i][l + 1] < factor[i][l + 1] - factor[i][l]) l -- ;
            if (l < 0) break;
            segment[ ++ cnt] = {1, factor[i][l], factor[i][r], i, 0};
        }
    }
    len = sqrt(cnt);
    sort(segment + 1, segment + cnt + 1, cmp1);
    for (int i = cnt; i; i -- )
    {
        if (segment[i].op)
        {
            sum[get(segment[i].r)] = max(sum[get(segment[i].r)], segment[i].d);
            w[segment[i].r] = max(w[segment[i].r], segment[i].d);
        }
        else segment[i].d = query(segment[i].l, segment[i].r);
    }
    sort(segment + 1, segment + cnt + 1, cmp2);
    for (int i = 1; i <= q; i ++ ) cout << segment[i].d << "\n";
    return 0;
}

/tmp/ccNDNLY6.o: in function `get(int)':
answer.code:(.text+0xba): relocation truncated to fit: R_X86_64_PC32 against symbol `len' defined in .bss section in /tmp/ccNDNLY6.o
/tmp/ccNDNLY6.o: in function `query(int, int)':
answer.code:(.text+0xc8): relocation truncated to fit: R_X86_64_PC32 against symbol `len' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text+0xf3): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text+0x14c): relocation truncated to fit: R_X86_64_PC32 against symbol `sum' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text+0x15d): relocation truncated to fit: R_X86_64_PC32 against symbol `sum' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text+0x1ae): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text+0x1be): relocation truncated to fit: R_X86_64_PC32 against symbol `w' defined in .bss section in /tmp/ccNDNLY6.o
/tmp/ccNDNLY6.o: in function `main':
answer.code:(.text.startup+0x2c): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text.startup+0x55): relocation truncated to fit: R_X86_64_PC32 against symbol `q' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text.startup+0x63): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccNDNLY6.o
answer.code:(.text.startup+0x72): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status