1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. /*
  6. ------------------------Input Checker----------------------------------
  7. */
  8.  
  9. long long readInt(long long l,long long r,char endd){
  10.     long long x=0;
  11.     int cnt=0;
  12.     int fi=-1;
  13.     bool is_neg=false;
  14.     while(true){
  15.         char g=getchar();
  16.         if(g=='-'){
  17.             assert(fi==-1);
  18.             is_neg=true;
  19.             continue;
  20.         }
  21.         if('0'<=g && g<='9'){
  22.             x*=10;
  23.             x+=g-'0';
  24.             if(cnt==0){
  25.                 fi=g-'0';
  26.             }
  27.             cnt++;
  28.             assert(fi!=0 || cnt==1);
  29.             assert(fi!=0 || is_neg==false);
  30.  
  31.             assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  32.         } else if(g==endd){
  33.             if(is_neg){
  34.                 x= -x;
  35.             }
  36.  
  37.             if(!(l <= x && x <= r))
  38.             {
  39.                 cerr << l << ' ' << r << ' ' << x << '\n';
  40.                 assert(1 == 0);
  41.             }
  42.  
  43.             return x;
  44.         } else {
  45.             assert(false);
  46.         }
  47.     }
  48. }
  49. string readString(int l,int r,char endd){
  50.     string ret="";
  51.     int cnt=0;
  52.     while(true){
  53.         char g=getchar();
  54.         assert(g!=-1);
  55.         if(g==endd){
  56.             break;
  57.         }
  58.         cnt++;
  59.         ret+=g;
  60.     }
  61.     assert(l<=cnt && cnt<=r);
  62.     return ret;
  63. }
  64. long long readIntSp(long long l,long long r){
  65.     return readInt(l,r,' ');
  66. }
  67. long long readIntLn(long long l,long long r){
  68.     return readInt(l,r,'\n');
  69. }
  70. string readStringLn(int l,int r){
  71.     return readString(l,r,'\n');
  72. }
  73. string readStringSp(int l,int r){
  74.     return readString(l,r,' ');
  75. }
  76.  
  77.  
  78. /*
  79. ------------------------Main code starts here----------------------------------
  80. */
  81.  
  82. const int MAX_T = 1e5;
  83. const int MAX_N = 1e5;
  84. const int MAX_SUM_LEN = 1e5;
  85.  
  86. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  87. #define ff first
  88. #define ss second
  89. #define mp make_pair
  90. #define ll long long
  91. #define rep(i,n) for(int i=0;i<n;i++)
  92. #define rev(i,n) for(int i=n;i>=0;i--)
  93. #define rep_a(i,a,n) for(int i=a;i<n;i++)
  94. #define pb push_back
  95.  
  96. ll sum_n = 0, sum_m = 0;
  97. int max_n = 0, max_m = 0;
  98. int yess = 0;
  99. int nos = 0;
  100. int total_ops = 0;
  101. ll mod = 998244353;
  102.  
  103. using ii = pair<ll,ll>;
  104.  
  105.  
  106.  
  107. void solve(){
  108.  
  109.    int n = readIntLn(2,3e5);
  110.    sum_n+=n;
  111.  
  112.    int g = 0;
  113.    int a[n], pg[n], sg[n];
  114.  
  115.    rep(i,n){
  116.     if(i<n-1) a[i] = readIntSp(1,1e9);
  117.     else a[i] = readIntLn(1,1e9);
  118.  
  119.     g = __gcd(g,a[i]);
  120.     pg[i] = g;
  121.    }
  122.  
  123.    int curr = 0, cnt = 0;
  124.    rev(i,n-1){
  125.     int tmp = curr;
  126.     if(i>0) tmp = __gcd(tmp, pg[i-1]);
  127.  
  128.     if(tmp>g || g>1) cnt++;
  129.     curr = __gcd(curr, a[i]);
  130.    }
  131.  
  132.    cout<<cnt<<'\n';
  133. }
  134.  
  135.  
  136.  
  137. signed main()
  138. {
  139.  
  140.     #ifndef ONLINE_JUDGE
  141.     freopen("input.txt", "r" , stdin);
  142.     freopen("output.txt", "w" , stdout);
  143.     #endif
  144.     fast;
  145.     
  146.     int t = 1;
  147.     
  148.     t = readIntLn(1,5e4);
  149.     
  150.     for(int i=1;i<=t;i++)
  151.     {    
  152.        solve();
  153.     }
  154.    
  155.     assert(getchar() == -1);
  156.     assert(sum_n<=3e5);
  157.  
  158.     cerr<<"SUCCESS\n";
  159.     cerr<<"Tests : " << t << '\n';
  160.     cerr<<"Sum of lengths : " << sum_n<<'\n';
  161.     //cerr<<"Maximum answer : " << max_n <<'\n';
  162.     // // cerr<<"Total operations : " << total_ops << '\n';
  163.     // cerr<<"Answered yes : " << yess << '\n';
  164.     // cerr<<"Answered no : " << nos << '\n';
  165.  
  166.     cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
  167. }