#include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int num[];

 int p[];

 int n;

 struct node

 {

     int l,r,id;

 } que[];

 bool cmp(node a,node b)

 {

     return a.r < b.r;

 }

 bool cmp1(node a,node b)

 {

     return a.id < b.id;

 }

 int pre[];

 int ans[];

 int lowbit(int t)

 {

     return t&(-t);

 }

 void insert(int t,int d)

 {

     while(t)

     {

         p[t] = max(p[t],d);

         t -= lowbit(t);

     }

 }

 int getmax(int t)

 {

     int maxz = ;

     while(t <= n)

     {

         maxz = max(maxz,p[t]);

         t += lowbit(t);

     }

     return maxz;

 }

 int main()

 {

     int i,j,t,m,tnum;

     scanf("%d",&t);

     while(t--)

     {

         memset(p,,sizeof(p));

         memset(pre,,sizeof(pre));

         scanf("%d",&n);

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

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

         scanf("%d",&m);

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

         {

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

             que[i].id = i;

         }

         sort(que,que+m,cmp);

         tnum = ;

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

         {

             if(tnum == m) break;

             for(j = ; j*j <= num[i]; j ++)

             {

                 if(num[i]%j == )

                 {

                     if(pre[j] != )

                         insert(pre[j],j);

                     pre[j] = i;

                     if (j * j== num[i]) continue ;

                     if(pre[num[i]/j] != )

                         insert(pre[num[i]/j],num[i]/j);

                     pre[num[i]/j] = i;

                 }

             }

             while(tnum < m&&que[tnum].r == i)

             {

                 ans[que[tnum].id] = getmax(que[tnum].l);

                 tnum ++;

             }

         }

         sort(que,que+m,cmp1);

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

         {

             if(que[i].l == que[i].r)

             printf("0\n");

             else

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

         }

     }

     return ;

 }