#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;#define N 50007int c[N];struct node{    int l,r,v;}a[10*N],Q[N];int n,pos[N],num[N],ans[N];int cmp(node ka,node kb) { return ka.r < kb.r; }int lowbit(int x) { return x&-x; }void modify(int x,int val){    while(x > 0)    {        c[x] = max(c[x],val);        x -= lowbit(x);    }}int getmax(int x){    int res = 0;    while(x <= n)    {        res = max(res,c[x]);        x += lowbit(x);    }    return res;}int main(){    int t,i,j,x,q,tot;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=1;i<=n;i++)        {            scanf("%d",&x);            pos[x] = i;            c[i] = 1;        }        tot = 0;        for(i=2;i<=n/2;i++)        {            int k = 0;            for(j=i;j<=n;j+=i)  //i的倍数                num[k++] = pos[j];            sort(num,num+k);            for(j=1;j<k;j++)            {                 a[tot].l = num[j-1];                 a[tot].r = num[j];                 a[tot++].v = i;            }        }        scanf("%d",&q);        for(i=0;i<q;i++)        {            scanf("%d%d",&Q[i].l,&Q[i].r);            Q[i].v = i;        }        sort(a,a+tot,cmp);        sort(Q,Q+q,cmp);        j = 0;        for(i=0;i<q;i++)        {            if(Q[i].l == Q[i].r)            {                ans[Q[i].v] = 0;                continue;            }            while(j < tot && a[j].r <= Q[i].r)                modify(a[j].l,a[j].v),j++;            ans[Q[i].v] = getmax(Q[i].l);        }        for(i=0;i<q;i++)            printf("%d\n",ans[i]);    }    return 0;}