#include <iostream>
using namespace std;
int gcd(int a, int b){
if(a==0)
return b;
return gcd(b%a, a);
}
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
// cout << endl;
int count[n]={0};
for(int i=0;i<n;i++){
int k=i;
for(int j=i+1;j<n;j++){
if(gcd(a[k],a[j])>1){
k=k+1;
count[i]++;
}
}
}
// for(int i=0;i<n;i++)
// cout << count[i];
int max=0;
for(int i=0;i<n;i++){
if(max<count[i])
max=count[i];
}
cout << max+1 << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGdjZChpbnQgYSwgaW50IGIpewoJaWYoYT09MCkKCQlyZXR1cm4gYjsKCXJldHVybiBnY2QoYiVhLCBhKTsKfQoKaW50IG1haW4oKXsKCWludCB0OwoJY2luID4+IHQ7Cgl3aGlsZSh0LS0pewoJCWludCBuOwoJCWNpbiA+PiBuOwoJCWludCBhW25dOwoJCWZvcihpbnQgaT0wO2k8bjtpKyspCgkJCWNpbiA+PiBhW2ldOwoJCS8vIGNvdXQgPDwgZW5kbDsKCQlpbnQgY291bnRbbl09ezB9OwoJCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCQlpbnQgaz1pOwoJCQlmb3IoaW50IGo9aSsxO2o8bjtqKyspewoJCQkJaWYoZ2NkKGFba10sYVtqXSk+MSl7CgkJCQkJaz1rKzE7CgkJCQkJY291bnRbaV0rKzsKCQkJCX0KCQkJfQoJCX0KCQkvLyBmb3IoaW50IGk9MDtpPG47aSsrKQoJCS8vIAljb3V0IDw8IGNvdW50W2ldOwoJCWludCBtYXg9MDsKCQlmb3IoaW50IGk9MDtpPG47aSsrKXsKCQkJaWYobWF4PGNvdW50W2ldKQoJCQkJbWF4PWNvdW50W2ldOwoJCX0KCQljb3V0IDw8IG1heCsxIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==