1 /**
  2 题意：求解区间[ L , R ]   max gcd() ;
  3 
  4 如果只求一次，那么我们可以这样做。
  5 把每个数字的因子刷一遍，满足>=2的最大就是结果。
  6 如果多次，可以这样求解。
  7 在区间[ L , R ] 如果素因子出现，更新它上次出现的位置的最大值，
  8 保存当前出现的位置。第一次出现不更新，只保存。
  9 
 10 当枚举到R的时候，我们就可以在[ L, R ]中找最大值即可。
 11 
 12 所以这一题就可以对r 排序，然后进行更新。
 13 **/
 14 #include<iostream>
 15 #include<stdio.h>
 16 #include<cstring>
 17 #include<cstdlib>
 18 #include<algorithm>
 19 #include<vector>
 20 using namespace std;
 21 
 22 vector<int>yz[50002];
 23 struct node
 24 {
 25     int l,r,len;
 26     int maxn;
 27 }f[50002*4];
 28 struct node2
 29 {
 30     int st,ed;
 31     int i,val;
 32 }a[50002];
 33 int date[50002];
 34 int pre[50002];
 35 
 36 bool cmp(struct node2 n1,struct node2 n2)
 37 {
 38     return n1.ed<n2.ed;
 39 }
 40 bool cmp1(struct node2 n1,struct node2 n2)
 41 {
 42     return n1.i<n2.i;
 43 }
 44 void init()
 45 {
 46     for(int i=1;i<=50000;i++)
 47         for(int j=i;j<=50000;j=j+i)
 48         yz[j].push_back(i);
 49 }
 50 void build(int l,int r,int n)
 51 {
 52     int mid = (l+r)/2;
 53     f[n].l = l;
 54     f[n].r = r;
 55     f[n].len = f[n].r-f[n].l +1;
 56     f[n].maxn = 0;
 57     if(l==r) return;
 58     build(l,mid,n*2);
 59     build(mid+1,r,n*2+1);
 60 }
 61 void update(int wz,int num,int n)
 62 {
 63     int mid=(f[n].l + f[n].r)/2;
 64     if(f[n].l == wz && f[n].r == wz)
 65     {
 66         if(f[n].maxn<num)
 67             f[n].maxn = num;
 68         return;
 69     }
 70     if(mid>=wz) update(wz,num,n*2);
 71     else if(mid<wz) update(wz,num,n*2+1);
 72     f[n].maxn = f[n*2].maxn>f[n*2+1].maxn ? f[n*2].maxn : f[n*2+1].maxn;
 73 }
 74 int query(int l,int r,int n)
 75 {
 76     int mid=(f[n].l + f[n].r)/2;
 77     if(f[n].l == l && f[n].r == r)
 78     {
 79         return f[n].maxn;
 80     }
 81     if(mid>=r) return query(l,r,n*2);
 82     else if(mid<l) return query(l,r,n*2+1);
 83     else return max(query(l,mid,n*2),query(mid+1,r,n*2+1));
 84 }
 85 int main()
 86 {
 87     int T , n , m;
 88     init();
 89     scanf("%d",&T);
 90     while(T--)
 91     {
 92         scanf("%d",&n);
 93         build(1,n,1);
 94         for(int i=1;i<=n;i++)
 95             scanf("%d",&date[i]);
 96         scanf("%d",&m);
 97         for(int i=1;i<=m;i++)
 98         {
 99             scanf("%d%d",&a[i].st,&a[i].ed);
100             a[i].i = i;
101             a[i].val = 0;
102         }
103         sort(a+1,a+1+m,cmp);
104         memset(pre,0,sizeof(pre));
105         int k = 1;
106         for(int i=1;i<=n;i++)
107         {
108             int ans = yz[date[i]].size();
109             for(int j=0;j<ans;j++)
110             {
111                 int temp = yz[date[i]][j];
112                 if(pre[temp])
113                     update(pre[temp],temp,1);
114                 pre[temp] = i;
115             }
116             while(a[k].ed == i && k<=m)
117             {
118                 a[k].val = query(a[k].st,a[k].ed,1);
119                 k++;
120             }
121         }
122         sort(a+1,a+1+m,cmp1);
123         for(int i=1;i<=m;i++)   printf("%d\n",a[i].val);
124     }
125     return 0;
126 }