/* dont stick to an approach */

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <unordered_map>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <bitset>
#include <chrono>
#include <random>
#include <fstream>

using namespace std;

typedef int ll;
typedef unsigned long long int ull;
typedef long double ldb;

#define PB push_back

#define For(i, n) for (ll i = 0; i < n; i++)

#define trav(a,x) for (auto& a : x)

#define PYES cout<<"YES\n"
#define PNO cout<<"NO\n"
#define PYes cout<<"Yes\n"
#define PNo cout<<"No\n"
//#define endl '\n'

#define sq(x)           (x*x)

#define vll             vector<ll>
#define pll             pair<ll,ll>
#define ff              first
#define ss              second
#define rev(v)          reverse(v.begin(),v.end())
#define srt(v)          sort(v.begin(),v.end())
#define grtsrt(v)       sort(v.begin(),v.end(),greater<ll>())
#define mnv(v)          *min_element(v.begin(),v.end())
#define mxv(v)          *max_element(v.begin(),v.end())
#define all(v)          v.begin(),v.end()
#define ACC(v)          accumulate(v.begin(),v.end(),0ll)

#define eps             1e-9

const double PI=acos(-1.0);

#define Fas ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());

//--------------------------------------------functions-------------------------------------------------//

ll power(ll a,ll b){ll result=1;while(b>0){if(b%2 == 1){result *= a;} a *= a;b /= 2;}return result;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
ll countSetBits(ll x){ll Count=0;while(x>0){if(x&1) Count++;x=x>>1;}return Count;}
bool isPerfectSquare(ll n){ll sr = sqrt(n);if (sr * sr == n)return true;else return false;}
ll mod(ll x,ll M){return ((x%M + M)%M);}
ll add(ll a, ll b,ll M){return mod(mod(a,M)+mod(b,M),M);}
ll mul(ll a, ll b,ll M){return mod(mod(a,M)*mod(b,M),M);}
ll powerM(ll a,ll b,ll M){
    ll res=1ll;
    while(b){
        if(b%2ll==1ll){
            res=mul(a,res,M);
        }
        a=mul(a,a,M);b/=2ll;
    }
    return res;
}
ll mod_inv(ll a, ll m) {
    ll g = m, r = a, x = 0, y = 1;
    while (r != 0) {
        ll q = g / r;
        g %= r; swap(g, r);
        x -= q * y; swap(x, y);
    }
    return mod(x,m);
}


//------------------------------------sieve of erantothenes-----------------------------------------------//
//ll MAXN=1e7+150;
//vector<ll> fact(MAXN+1);
//void sieve_of_erantothenes()
//{
//    fact[1] = 1;
//    for (ll i = 2; i <= MAXN; i++)
//        fact[i] = i;
//    for (ll i = 4; i <= MAXN; i += 2)
//        fact[i] = 2;
//    for (ll i = 3; i * i <= MAXN; i++){
//        if (fact[i] == i){
//            for (ll j = i * i; j <= MAXN; j += i)
//                if (fact[j] == j)
//                    fact[j] = i;
//        }
//    }
//}
//----------------------------------------nCr mod------------------------------------------------------//
ll nCr(ll n, ll k){
    if(n<k) return 0;
    if(k==0) return 1;
    ll res = 1;
    if (k > n - k) k = n - k;
    for(ll i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

ll modInverse(ll n,ll M){
    return powerM(n,M-2,M);
}

vector<ll> factu;
void factcalc(ll n,ll M){
    factu.resize(n+1);
    factu[0]=1;
    for(ll i=1;i<=n;i++){
        factu[i]=mul(factu[i-1],i,M);
    }
}
ll nCrM(ll n,ll r,ll M){
    if(n<r) return 0;
    if(r==0) return 1;
    return mul(mul(factu[n],modInverse(factu[r],M),M),modInverse(factu[n-r],M),M);
}
ll rand_int(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}
//-----------------------------------------------solve-----------------------------------------------------//
vll seg;
vll v;

void build(ll ind,ll low,ll high){
    if(low==high){
        seg[ind]=v[low];
        return;
    }
    ll mid=(low+high)/2;
    build(2*ind+1,low,mid);
    build(2*ind+2,mid+1,high);
    seg[ind]=gcd(seg[2*ind+1],seg[2*ind+2]);
}

ll query(ll ind,ll low,ll high,ll l,ll r){
    if(low>=l && high<=r){
        return seg[ind];
    }
    if(high<l || low>r){
        return 0;
    }
    ll mid=(low+high)/2;
    ll left=query(2*ind+1,low,mid,l,r);
    ll right=query(2*ind+2,mid+1,high,l,r);
    return gcd(left,right);
}

void solve(){
    ll n;cin>>n;
    seg.resize(4*2*n+3);
    v.resize(2*n+5);
    for(ll i=0;i<n;i++){
        cin>>v[i];
    }
    ll g=0;
    for(ll i=0;i<n;i++){
        v[n+i]=v[i];
    }
    for(ll i=0;i<n;i++){
        g=gcd(g,v[i]);
    }
    ll g1=v[0];
    ll ind=0;
    while(g1!=g){
        ind++;
        g1=gcd(g1,v[ind]);
    }
    build(0,0,2*n+1);
    ll ans=ind+1;
    for(ll i=1;i<n;i++){
        ind=max(i,ind);
        while (query(0,0,2*n+1,i,ind)!=g) {
            ind++;
        }
        ans=max(ans,ind-i+1);
    }
    cout<<ans-1<<endl;
    seg.clear();
    v.clear();
}


int main(){
    Fas;

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cout<<fixed<<setprecision(20);
    
    ll t=0;
    cin>>t;
    while (t--)
    
       solve();
    
    return 0;
}

### Prompt

Create a solution in CPP for the following problem:

You are given an array of positive integers a = [a_0, a_1, ..., a_{n - 1}] (n ≥ 2).

In one step, the array a is replaced with another array of length n, in which each element is the [greatest common divisor (GCD)](http://tiny.cc/tuy9uz) of two neighboring elements (the element itself and its right neighbor; consider that the right neighbor of the (n - 1)-th element is the 0-th element).

Formally speaking, a new array b = [b_0, b_1, ..., b_{n - 1}] is being built from array a = [a_0, a_1, ..., a_{n - 1}] such that b_i = \gcd(a_i, a_{(i + 1) mod n}), where \gcd(x, y) is the greatest common divisor of x and y, and x mod y is the remainder of x dividing by y. In one step the array b is built and then the array a is replaced with b (that is, the assignment a := b is taking place).

For example, if a = [16, 24, 10, 5] then b = [\gcd(16, 24), \gcd(24, 10), \gcd(10, 5), \gcd(5, 16)] = [8, 2, 5, 1]. Thus, after one step the array a = [16, 24, 10, 5] will be equal to [8, 2, 5, 1].

For a given array a, find the minimum number of steps after which all values a_i become equal (that is, a_0 = a_1 = ... = a_{n - 1}). If the original array a consists of identical elements then consider the number of steps is equal to 0.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case contains two lines. The first line contains an integer n (2 ≤ n ≤ 2 ⋅ 10^5) — length of the sequence a. The second line contains n integers a_0, a_1, ..., a_{n - 1} (1 ≤ a_i ≤ 10^6).

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

Print t numbers — answers for each test case.

Example

Input


5
4
16 24 10 5
4
42 42 42 42
3
4 6 4
5
1 2 3 4 5
6
9 9 27 9 9 63


Output


3
0
2
1
1

### Response

```cpp
/* dont stick to an approach */

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <unordered_map>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <bitset>
#include <chrono>
#include <random>
#include <fstream>

using namespace std;

typedef int ll;
typedef unsigned long long int ull;
typedef long double ldb;

#define PB push_back

#define For(i, n) for (ll i = 0; i < n; i++)

#define trav(a,x) for (auto& a : x)

#define PYES cout<<"YES\n"
#define PNO cout<<"NO\n"
#define PYes cout<<"Yes\n"
#define PNo cout<<"No\n"
//#define endl '\n'

#define sq(x)           (x*x)

#define vll             vector<ll>
#define pll             pair<ll,ll>
#define ff              first
#define ss              second
#define rev(v)          reverse(v.begin(),v.end())
#define srt(v)          sort(v.begin(),v.end())
#define grtsrt(v)       sort(v.begin(),v.end(),greater<ll>())
#define mnv(v)          *min_element(v.begin(),v.end())
#define mxv(v)          *max_element(v.begin(),v.end())
#define all(v)          v.begin(),v.end()
#define ACC(v)          accumulate(v.begin(),v.end(),0ll)

#define eps             1e-9

const double PI=acos(-1.0);

#define Fas ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());

//--------------------------------------------functions-------------------------------------------------//

ll power(ll a,ll b){ll result=1;while(b>0){if(b%2 == 1){result *= a;} a *= a;b /= 2;}return result;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
ll countSetBits(ll x){ll Count=0;while(x>0){if(x&1) Count++;x=x>>1;}return Count;}
bool isPerfectSquare(ll n){ll sr = sqrt(n);if (sr * sr == n)return true;else return false;}
ll mod(ll x,ll M){return ((x%M + M)%M);}
ll add(ll a, ll b,ll M){return mod(mod(a,M)+mod(b,M),M);}
ll mul(ll a, ll b,ll M){return mod(mod(a,M)*mod(b,M),M);}
ll powerM(ll a,ll b,ll M){
    ll res=1ll;
    while(b){
        if(b%2ll==1ll){
            res=mul(a,res,M);
        }
        a=mul(a,a,M);b/=2ll;
    }
    return res;
}
ll mod_inv(ll a, ll m) {
    ll g = m, r = a, x = 0, y = 1;
    while (r != 0) {
        ll q = g / r;
        g %= r; swap(g, r);
        x -= q * y; swap(x, y);
    }
    return mod(x,m);
}


//------------------------------------sieve of erantothenes-----------------------------------------------//
//ll MAXN=1e7+150;
//vector<ll> fact(MAXN+1);
//void sieve_of_erantothenes()
//{
//    fact[1] = 1;
//    for (ll i = 2; i <= MAXN; i++)
//        fact[i] = i;
//    for (ll i = 4; i <= MAXN; i += 2)
//        fact[i] = 2;
//    for (ll i = 3; i * i <= MAXN; i++){
//        if (fact[i] == i){
//            for (ll j = i * i; j <= MAXN; j += i)
//                if (fact[j] == j)
//                    fact[j] = i;
//        }
//    }
//}
//----------------------------------------nCr mod------------------------------------------------------//
ll nCr(ll n, ll k){
    if(n<k) return 0;
    if(k==0) return 1;
    ll res = 1;
    if (k > n - k) k = n - k;
    for(ll i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

ll modInverse(ll n,ll M){
    return powerM(n,M-2,M);
}

vector<ll> factu;
void factcalc(ll n,ll M){
    factu.resize(n+1);
    factu[0]=1;
    for(ll i=1;i<=n;i++){
        factu[i]=mul(factu[i-1],i,M);
    }
}
ll nCrM(ll n,ll r,ll M){
    if(n<r) return 0;
    if(r==0) return 1;
    return mul(mul(factu[n],modInverse(factu[r],M),M),modInverse(factu[n-r],M),M);
}
ll rand_int(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}
//-----------------------------------------------solve-----------------------------------------------------//
vll seg;
vll v;

void build(ll ind,ll low,ll high){
    if(low==high){
        seg[ind]=v[low];
        return;
    }
    ll mid=(low+high)/2;
    build(2*ind+1,low,mid);
    build(2*ind+2,mid+1,high);
    seg[ind]=gcd(seg[2*ind+1],seg[2*ind+2]);
}

ll query(ll ind,ll low,ll high,ll l,ll r){
    if(low>=l && high<=r){
        return seg[ind];
    }
    if(high<l || low>r){
        return 0;
    }
    ll mid=(low+high)/2;
    ll left=query(2*ind+1,low,mid,l,r);
    ll right=query(2*ind+2,mid+1,high,l,r);
    return gcd(left,right);
}

void solve(){
    ll n;cin>>n;
    seg.resize(4*2*n+3);
    v.resize(2*n+5);
    for(ll i=0;i<n;i++){
        cin>>v[i];
    }
    ll g=0;
    for(ll i=0;i<n;i++){
        v[n+i]=v[i];
    }
    for(ll i=0;i<n;i++){
        g=gcd(g,v[i]);
    }
    ll g1=v[0];
    ll ind=0;
    while(g1!=g){
        ind++;
        g1=gcd(g1,v[ind]);
    }
    build(0,0,2*n+1);
    ll ans=ind+1;
    for(ll i=1;i<n;i++){
        ind=max(i,ind);
        while (query(0,0,2*n+1,i,ind)!=g) {
            ind++;
        }
        ans=max(ans,ind-i+1);
    }
    cout<<ans-1<<endl;
    seg.clear();
    v.clear();
}


int main(){
    Fas;

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cout<<fixed<<setprecision(20);
    
    ll t=0;
    cin>>t;
    while (t--)
    
       solve();
    
    return 0;
}

```