t l,r,maxx,add,mid;
}tree[MAX*4];
void up(int x) {
tree[x].maxx = max(tree[ll(x)].maxx,tree[rr(x)].maxx);
}
void down(int x) {
if(tree[x].add != 0) {
tree[ll(x)].add = max(tree[x].add,tree[ll(x)].add);
tree[rr(x)].add = max(tree[x].add,tree[rr(x)].add);
tree[ll(x)].maxx = max(tree[x].add,tree[ll(x)].maxx);
tree[rr(x)].maxx = max(tree[x].add,tree[rr(x)].maxx);
tree[x].add = 0;
}
}
void build(int l,int r,int x) {
tree[x].l = l;
tree[x].r = r;
tree[x].mid = (l+r) >> 1;
tree[x].maxx = 0;
tree[x].add = 0;
if(l == r) return ;
build(l,tree[x].mid,ll(x));
build(tree[x].mid+1,r,rr(x));
}
void update(int l,int r,int x,int t) {
if(l <= tree[x].l && r >= tree[x].r) {
tree[x].add = max(t,tree[x].add);
tree[x].maxx = max(tree[x].maxx,tree[x].add);
return ;
}
down(x);
if(r <= tree[x].mid) update(l,r,ll(x),t);
else if(l > tree[x].mid) update(l,r,rr(x),t);
else {
update(l,tree[x].mid,ll(x),t);
update(tree[x].mid+1,r,rr(x),t);
}
up(x);
}
int query(int l,int x) {
if(tree[x].l == tree[x].r) {
return tree[x].maxx;
}
down(x);
if(l > tree[x].mid) return query(l,rr(x));
else return query(l,ll(x));
}
int main() {
int T;
cin >> T;
init();
while( T--) {
RD(n);
build(1,n,1);
memset(pos,0,sizeof(pos));
for(int i=1; i<=n; i++) RD(a[i]);
RD(q);
for(int i=1; i<=q; i++) {
RD(ask[i].l);
RD(ask[i].r);
ask[i].num = i;
}
sort(ask+1,ask+1+q,cmp);
int cnt = 1,flag = 0;
for(int i=1; i<=n; i++) {
for(int j=head[a[i]]; j != -1; j = v[j].next) {
int t = v[j].e;
if(pos[t] != 0) update(1,pos[t],1,t);
pos[t] = i;
}
while(ask[cnt].r <= i) {
print[ask[cnt].num] = query(ask[cnt].l,1);
cnt++;
if(cnt > q) {
flag = 1;
break;
}
}
if(flag) break;
}
for(int i=1; i<=q; i++) OT(print[i]),puts("");
}
return 0;
}
#include
#include
#include
#include
#include
#include
# define MAX 51111
# define ll(x) x << 1
# define rr(x) x << 1 | 1
using namespace std;
inline void RD(int &ret) {
char c;
do {
c = getchar();
} while(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
int a[MAX],pos[MAX],print[MAX];
struct node {
int l,r;
int num;
}ask[MAX];
struct Node {
int s,e,next;
}v[1111111];
int head[MAX];
int n,q,num = 0;
void addedge(int s,int e) {
v[num].s = s;
v[num].e = e;
v[num].next = head[s];
head[s] = num++;
}
void init() { //预处理
memset(head,-1,sizeof(head));
for(int i=1; i<=50000; i++) {
for(int j=i; j<=50000; j+=i) {
addedge(j,i);
}
}
}
bool cmp(node a,node b) {
return a.r < b.r;
}
struct Tree {
int l,r,maxx,add,mid;
}tree[MAX*4];
void up(int x) {
tree[x].maxx = max(tree[ll(x)].maxx,tree[rr(x)].maxx);
}
void down(int x) {
if(tree[x].add != 0) {
tree[ll(x)].add = max(tree[x].add,tree[ll(x)].add);
tree[rr(x)].add = max(tree[x].add,tree[rr(x)].add);
tree[ll(x)].maxx = max(tree[x].add,tree[ll(x)].maxx);
tree[rr(x)].maxx = max(tree[x].add,tree[rr(x)].maxx);
tree[x