Life is a game,and you lose it,so you suicide. 

But you can not kill yourself before you solve this problem: 

Given you a sequence of number a ₁, a ₂, ..., a _n.They are also a permutation of 1...n. 

You need to answer some queries,each with the following format: 

If we chose two number a,b (shouldn't be the same) from interval [l, r],what is the maximum gcd(a, b)? If there's no way to choose two distinct number(l=r) then the answer is zero.

 

First line contains a number T(T <= 5),denote the number of test cases. 

Then follow T test cases. 

For each test cases,the first line contains a number n(1 <= n <= 50000). 

The second line contains n number a ₁, a ₂, ..., a _n. 

The third line contains a number Q(1 <= Q <= 50000) denoting the number of queries. 

Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n),denote a query.

 

For each test cases,for each query print the answer in one line.

 

1

10

8 2 4 9 5 7 10 6 1 3

5

2 10

2 4

6 9

1 4

7 10 

 

5

2

2

4

3 

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define lson rt << 1, l, mid

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

#define root 1, 1, N

const int MAXN = 5e4 + 5;

int T, N, A[MAXN], Q, pre[MAXN], Sum[MAXN << 2], ans[MAXN];

struct qeu {

    int l, r, id;

    bool operator < (const qeu & a) const {

        return r < a.r;

    }

} QS[MAXN];

vector<int>G[MAXN];

void init() {

    for(int i = 1; i < MAXN; i ++) {

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

            G[j].push_back(i);

        }

    }

}

void pushup(int rt) {

    Sum[rt] = max(Sum[rt << 1], Sum[rt << 1|1]);

}

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

    Sum[rt] = 0;

    if(l == r) return ;

    int mid = (l + r) >> 1;

    build(lson);

    build(rson);

}

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

    if(l == r) {

        Sum[rt] = max(Sum[rt], v);

        return;

    }

    int mid = (l + r) >> 1;

    if(p <= mid) update(p, v, lson);

    else update(p, v, rson);

    pushup(rt);

}

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

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

        return Sum[rt];

    }

    int mid = (l + r) >> 1;

    int ret = 0;

    if(L <= mid) ret = max(ret, query(L, R, lson));

    if(R > mid) ret = max(ret, query(L, R, rson));

    return ret;

}

int main() {

    init();

    //freopen("D://imput.txt", "r", stdin);

    scanf("%d", &T);

    while(T --) {

        scanf("%d", &N);

        build(root);

        for(int i = 1; i <= N; i ++) {

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

        }

        scanf("%d", &Q);

        for(int i = 1; i <= Q; i ++) {

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

            QS[i].id = i;

        }

        memset(pre, -1, sizeof(pre));

        sort(QS + 1, QS + Q + 1);

        for(int i = 1, j = 1; i <= N && j <= Q; i ++) {

            for(int k = 0 ; k < G[A[i]].size(); k ++) {

                int tmp = G[A[i]][k];

                if(pre[tmp] != -1) {

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

                }

                pre[tmp] = i;

            }

            while(j <= Q && QS[j].r == i) {

                ans[QS[j].id] = query(QS[j].l, QS[j].r, root);

                j ++;

            }

        }

        for(int i = 1; i <= Q; i ++) {

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

        }

    }

    return 0;

}