#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<string.h>
#include<set>
#include<map>
#define LL long long
#define pr pair<int,int>
#define fr first
#define sc second
//#define mp make_pair
using namespace std;
LL read( ){LL sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) return -sum;return sum;}
void read(int &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
void read(LL &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
const int N=500005;
int n,a[N],b[N],p[N];
int gcd(int x,int y) {return y?gcd(y, x%y):x;}
int main( )
{
int i,x,y,L,R,T=read( );
while(T--)
{
read(n);
for(i=1;i<=n;i++) read(a[i]);
int cnt=0, ans=0;
for(i=1;i<=n;i++)
{
x=i;
y=(x==n?1:x+1);
if(a[x]!=a[y]) p[++cnt]=x;
}
while(cnt)
{
for(i=1;i<=cnt;i++)
{
x=p[i];
y=(x==n?1:x+1);
b[x]=gcd(a[x],a[y]);
}
set<int>S;
for(i=1;i<=cnt;i++)
{
x=p[i];
a[x]=b[x];
}
for(i=1;i<=cnt;i++)
{
x=p[i];
R=(x==n?1:x+1);
L=(x==1?n:x-1);
if(a[x]!=a[R] && a[x]!=1) S.insert(x);
if(a[L]!=a[x] && a[L]!=1) S.insert(L);
}
ans++;cnt=0;
for(auto &x:S) p[++cnt]=x;
if(!cnt) break;
}
printf("%d\n",ans);
}
return 0;
}