#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()

const int mxN = (int)6e5+10;
const int C = (int)1e5+10;

int n;
stack<int> S;
int lst[C], cnt[C];
vector<int> v[C], D[C];
int a[mxN], pr1[mxN], pr2[mxN], nx1[mxN], nx2[mxN];

void solve(){
	cin >> n; 
	for(int i = 0; i < n; i++){
		cin >> a[i]; cnt[a[i]]=0;
		v[a[i]].clear(), lst[a[i]]=-1;
	}

	fill(pr1,pr1+n,-1); fill(pr2,pr2+n,-1);
	for(int i = 0; i < n; i++) v[a[i]].pb(i), nx1[i]=nx2[i]=n;
	
	S=stack<int>();
	for(int i = 0; i < n; i++){
		while(sz(S) and a[S.top()]>=a[i]) S.pop();
		if(sz(S)) pr1[i] = S.top();
		S.push(i);
	}
	S=stack<int>();
	for(int i = 0; i < n; i++){
		while(sz(S) and a[S.top()]<=a[i]) S.pop();
		if(sz(S)) pr2[i] = S.top();
		S.push(i);
	}
	S=stack<int>();
	for(int i = n-1; i >= 0; i--){
		while(sz(S) and a[S.top()]>=a[i]) S.pop();
		if(sz(S)) nx1[i] = S.top();
		S.push(i);
	}
	S=stack<int>();
	for(int i = n-1; i >= 0; i--){
		while(sz(S) and a[S.top()]<=a[i]) S.pop();
		if(sz(S)) nx2[i] = S.top();
		S.push(i);
	}
	
	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int x : D[a[i]]){
			int j = lst[x], k = -1, j2, k2;
			if(cnt[x]<sz(v[x])) k=v[x][cnt[x]];
			if(j==-1 or j<=pr2[i] or nx1[j]<=i) j=-1;
			if(k==-1 or nx2[i]<=k or pr1[k]>=i) k=-1;
			if(j==-1 and k==-1) continue;

			if(j==-1) j2=max(pr2[i]+1,pr1[k]+1);
			else j2=max(pr2[i]+1,pr1[j]+1);
			
			if(k==-1) k2 = min(nx2[i]-1, nx1[j]-1);
			else k2=min(nx2[i]-1,nx1[k]-1);

			ans = max(ans, k2-j2+1);
		}
		cnt[a[i]]++; lst[a[i]]=i;
	}
	cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    for(int i = 1; i < C; i++)
		for(int j = i; j < C; j+=i)
			D[j].pb(i);
    int t = 1; cin >> t;
    while(t--) solve();		
}