#include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 struct node

 {

     int l, r;

     int idx;

 };

 node Qry[MAXN];  //查询

 int C[MAXN];     //树状数组

 int vis[MAXN];   // i 的倍数上一次出现的位置

 int num[MAXN];   //原数组

 int ans[MAXN];   //答案

 int N, Q;

 bool cmp( node a, node b )

 {

     return a.l > b.l;

 }

 int lowbit( int x )

 {

     return x & (-x);

 }

 int query( int x )

 {

     int res = ;

     while ( x >  )

     {

         res = max( res, C[x] );

         x -= lowbit(x);

     }

     return res;

 }

 void Add( int x, int val )

 {

     while ( x <= N )

     {

         C[x] = max( C[x], val );

         x += lowbit(x);

     }

     return;

 }

 int main()

 {

     int T;

     scanf( "%d", &T );

     while ( T-- )

     {

         scanf( "%d", &N );

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

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

         scanf( "%d", &Q );

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

         {

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

             Qry[i].idx = i;

         }

         sort( Qry, Qry + Q, cmp );

         memset( C, , sizeof(C) );

         memset( vis, , sizeof(vis) );

         int i = , j = N;

         while ( i < Q )

         {

             while ( j >  && j >= Qry[i].l )

             {

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

                 {

                     if ( num[j] % k ==  )

                     {

                         if ( vis[k] )

                         {

                             Add( vis[k], k );

                         }

                         vis[k] = j;

                         int tmp = num[j] / k;

                         if ( tmp != k )

                         {

                             if ( vis[tmp] )

                             {

                                 Add( vis[tmp], tmp );

                             }

                             vis[tmp] = j;

                         }

                     }

                 }

                 --j;

             }

             ans[ Qry[i].idx ] = query( Qry[i].r );

             ++i;

         }

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

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

     }

     return ;

 }