#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int maxn = 5e4+;

int maxx[maxn<<], ans[maxn], a[maxn], b[maxn][], num[maxn], pre[maxn], c[maxn];

struct node

{

    int l, r, id;

    bool operator < (node a) const

    {

        return r<a.r;

    }

}q[maxn];

void build(int l, int r, int rt) {

    maxx[rt] = ;

    if(l == r)

        return ;

    int m = l+r>>;

    build(lson);

    build(rson);

}

void update(int p, int val, int l, int r, int rt) {

    if(l == r) {

        maxx[rt] = max(val, maxx[rt]);

        return ;

    }

    int m = l+r>>;

    if(p<=m)

        update(p, val, lson);

    else

        update(p, val, rson);

    maxx[rt] = max(maxx[rt<<], maxx[rt<<|]);

}

int query(int L, int R, int l, int r, int rt) {

    if(L<=l&&R>=r) {

        return maxx[rt];

    }

    int m = l+r>>, ret = ;

    if(L<=m)

        ret = max(ret, query(L, R, lson));

    if(R>m)

        ret = max(ret, query(L, R, rson));

    return ret;

}

int main()

{

    int t, n, m;

    cin>>t;

    while(t--) {

        mem(maxx);

        scanf("%d", &n);

        build(, n, );

        for(int i = ; i<=n; i++)

            scanf("%d", &a[i]);

        scanf("%d", &m);

        for(int i = ; i<m; i++) {

            scanf("%d%d", &q[i].l, &q[i].r);

            q[i].id = i;

        }

        sort(q, q+m);

        mem(num);

        mem(b);

        for(int i = ; i<=n; i++) {

            for(int j = i; j<=n; j+=i) {

                b[j][num[j]++] = i;

            }

        }

        mem1(pre);

        int pos = ;

        for(int i = ; i<=n&&pos<m; i++) {

            for(int j = ; j<num[a[i]]; j++) {

                int tmp = b[a[i]][j];

                if(~pre[tmp]) {

                    update(pre[tmp], tmp, , n, );

                }

                pre[tmp] = i;

            }

            while(q[pos].r == i) {

                if(q[pos].r == q[pos].l)

                    ans[q[pos].id] = ;

                else

                    ans[q[pos].id] = query(q[pos].l, q[pos].r, , n, );

                pos++;

            }

        }

        for(int i = ; i<m; i++) {

            printf("%d\n", ans[i]);

        }

    }

    return ;

}