#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int w1[101][101];
int w2[101][101];
int w3[101][101];
int A[101];
int Log(int x,int y){
	int ad=x;
	int sum=1;
	while(ad<=y){
		ad*=x;
		sum++;
	}
	return sum;
}
int main(){
	freopen("series.in","r",stdin);
	freopen("series.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				w1[i][j]=w2[i][j]=w3[i][j]=1;
			}
		for(int i=1;i<=n;i++)
			cin>>A[i];
		int ans=0;
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if((A[k]-A[i])/w1[i][k]==(A[j]-A[k])/w1[k][j]){
						w1[i][j]=max(w1[i][j],w1[i][k]+w1[k][j]);
						ans=max(w1[i][j],ans);
					}
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if((A[k]/A[i])/w2[i][k]==(A[j]/A[k])/w2[k][j]&&A[k]%A[i]==0&&A[j]%A[k]==0){
						w2[i][j]=max(w2[i][j],w2[i][k]+w2[k][j]);
						ans=max(w2[i][j],ans);
					}
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(A[i]!=1&&A[k]!=1&&A[j]!=1)
					if(Log(A[i],A[k])/w3[i][k]==Log(A[k],A[j])/w3[k][j]){
						w3[i][j]=max(w3[i][j],w3[i][k]+w3[k][j]);
						ans=max(w3[i][j],ans);
					}
		cout<<ans<<endl;
	}
return 0;
}