#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PB push_back
#define FI first
#define SE second
#define MP make_pair
#define ALL(cont) cont.begin(), cont.end()
#define MOD 1000000007ll

int memo[1000100];

int mexer(unordered_set<int>&mex)
{
    int pr = 0;
    while(mex.find(pr)!=mex.end())
        pr++;
    return pr;
}

void getdivisors(int m, vector<int>&div)
{
    // div WILL HAVE ALL DIVISORS IN SORTED ORDER EXCEPT 1 AMD m
    vector<int>sorted;
    for(int i=2;i*i<=m;i++)
    {
        if(m%i==0)
        {
            if(i*i==m)
                div.PB(i);
            else
            {
                div.PB(i);
                sorted.PB(m/i);
            }
        }
    }
    int n = sorted.size();
    for(int i=n-1;i>-1;i--)
        div.PB(sorted[i]);
}

void grundy(int m)
{
    if(memo[m]!=-1)
        return;
    
    vector<int>div;
    getdivisors(m,div);
   
    // PRIME NUBERS GRUNDY 0 AS NO REACHABLE STATE SO MEX(PHI) = 0
    if(div.size()==0)
    {
        memo[m]=0;
        return;
    }
    
    unordered_set<int>mex;

    // INTO it PILES EACH OF SIZE m/it
    for(auto it:div)
    {
        
        // EVEN NUMBER OF XORS RESULTING IN 0
        if(it%2==0)
        {
            mex.insert(0);
        }
        else
        {
            if(memo[m/it]==-1)
                grundy(m/it);
            mex.insert(memo[m/it]);
        }
    }
    memo[m] = mexer(mex);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    for(int i=0;i<1000100;i++)
        memo[i] = -1;
    memo[0] = 0;
    memo[1] = 0;

    // for(int i=0;i<1000100;i++)
    //     grundy(i);

    // for(int i=0;i<1000100;i++)
    //     cout<<i<<": "<<memo[i]<<endl;

    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int arr[n];
        int res = 0;
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            if(memo[arr[i]]==-1)
                grundy(arr[i]);
            res ^= memo[arr[i]];
        }
        if(res==0)
            cout<<2<<endl;
        else
            cout<<1<<endl;
    }



    return 0;


}