#include<bits/stdc++.h> using namespace std; int n,a[100005],__,st[19][100005]; struct sss{ int x,i,yi; bool operator<(const sss a)const{ return a.x<x; } }; inline int ch(int l,int r){ int md=__lg(r-l+1); if(st[md][l]*st[md][r-(1<<md)+1]/__gcd(st[md][l],st[md][r-(1<<md)+1])<1300000+7 && st[md][l]>=0 && st[md][r-(1<<md)+1]>=0)return st[md][l]/__gcd(st[md][l],st[md][r-(1<<md)+1])*st[md][r-(1<<md)+1]; return -1; } priority_queue<sss>q; int main(){ scanf("%d",&__); while(__--){ scanf("%d",&n); while(!q.empty())q.pop(); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); q.push((sss){a[i],i,i}); st[0][i]=a[i]; for(int j=1;j<=18;j++)st[j][i]=-1; } for(int i=1;i<=18;i++){ for(int j=1;j<=n;j++){ if(j+(1<<i)-1<=n && st[i-1][j]*st[i-1][j+(1<<(i-1))]/__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))])<1300000+7 && st[i-1][j]>0 && st[i-1][j+(1<<(i-1))]>0)st[i][j]=st[i-1][j]/__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))])*st[i-1][j+(1<<(i-1))]; if(st[i][j]<0 || st[i][j]>1300000+7)st[i][j]=-1; } } int last=0; while(!q.empty()){ sss now=q.top(); q.pop(); if(now.x>last+1)break; last=max(last,now.x); int l=now.yi+1,r=n; sss ans=((sss){-1,-1,-1}); while(l<=r){ int mid=(l+r)>>1; if(ch(now.i,mid)>1300000+7 || ch(now.i,mid)<0){ r=mid-1; } else if(ch(now.i,mid)!=now.x){ ans=((sss){ch(now.i,mid),now.i,mid}); r=mid-1; } else l=mid+1; } if(ans.i!=-1){ q.push(ans); } } printf("%d\n",last+1); } }