#include<bits/stdc++.h>
using namespace std;
//对于值为1的情况单独处理
//维护两边不为1的最新值。然后将1改为左右相乘的值，修改数加1
//剩下的根据两边的关系进行处理，有两个相邻的互质关系，可以修改中间值为两边的乘积，仅计一次
//不相邻计入总数即可
int main(){
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<int> nums(n);
        for(int i=0;i<n;i++)cin>>nums[i];
        int tol = 0;
        vector<int> ldp(n,1),rdp(n,1);
        for(int i=0;i<n;i++)if(nums[i]!=1)ldp[i]=nums[i];else if(i>0)ldp[i]=ldp[i-1];
        for(int i=n-1;i>=0;i--)if(nums[i]!=1)rdp[i]=nums[i];else if(i<n-1)rdp[i]=rdp[i+1];
        if(ldp[0]*rdp[0]==1){cout<<n<<endl;continue;}
        for(int i=0;i<n;i++)if(nums[i]==1){nums[i]=ldp[i]*rdp[i];tol++;}
        vector<bool> bl(n-1,true);
        for(int i=0;i<n-1;i++)if(gcd(nums[i],nums[i+1])==1)bl[i]=false;
        for(int i=0;i<n-2;i++)if(!(bl[i]||bl[i+1])){
            tol++;bl[i]=true;bl[i+1]=true;
        }
        for(int i=0;i<n-1;i++)if(!bl[i])tol++;
        cout<<tol<<endl;
    }
    return 0;
}