
题目大意:给你n个数,q次询问,每次询问区间[l, r],问a[i]%a[i + 1] % a[i + 2]...%a[j](j <= r)的值
思路:st预处理维护,再二分区间,复杂度n*(logn)*logn
//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const int maxn = 1e5 + ;
int a[maxn];
int st[maxn][];
int n; void init(){
for (int i = ; i < n; i++) st[i][] = a[i];
for (int j = ; ( << j) <= n; j++){
for (int i = ; i + ( << j) - < n; i++){
st[i][j] = min(st[i + ( << (j-))][j - ], st[i][j - ]);
}
}
} inline int query(int l, int r){
int len = r - l + ;
int k = ;
while (( << (k + )) <= len) k++;
return min(st[l][k], st[r - ( << k) + ][k]);
} inline int solve(){
int l, r;
scanf("%d%d", &l, &r);
l--, r--;
if (l == r) return a[l];
int val = a[l];
///二分区间
l++;
while (l <= r){
int lb = l, rb = r;
while (lb < rb){
int mid = (lb + rb) / ;
if (query(lb, mid) <= val) rb = mid;
else if (query(mid + , rb) <= val) lb = mid + ;
else return val;
}
l = lb + ;
val %= a[lb];
}
return val;
} int main(){
int t; scanf("%d", &t);
while (t--){
scanf("%d", &n);
for (int i = ; i < n; i++){
scanf("%d", a + i);
}
init();
int q; scanf("%d", &q);
while (q--){
printf ("%d\n", solve());
}
}
return ;
}