#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
#define SIZE 100100ll

vector<ll>divisors[SIZE];

void divisorscalc()
{
    for (ll i = 2; i < SIZE; i++)
    {
        for (ll j = i; j < SIZE; j += i)
            divisors[j].PB(i);
    }
}

ll mexer(unordered_set<ll>&s)
{
    ll x = 0;
    while (s.find(x) != s.end())
        x++;
    return x;
}

ll memo[SIZE];
void grundy(ll m)
{
    if (memo[m] != -1)
        return;
    unordered_set<ll>mex;
    for (auto it : divisors[m])
    {
        if (memo[m / it] == -1)
            grundy(m / it);
        if (it % 2 == 0)
            mex.insert(0);
        else
            mex.insert(memo[m / it]);
    }
    memo[m] = mexer(mex);
}


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




    divisorscalc();
    for (ll i = 0; i < SIZE; i++)
        memo[i] = -1;
    memo[0] = 0;
    memo[1] = 0;
    for (ll i = 2; i < SIZE; i++)
    {
        if (memo[i] == -1)
            grundy(i);
    }

    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];
            res ^= memo[arr[i]];
        }
        if (res == 0)
            cout << 2 << endl;
        else
            cout << 1 << endl;
    }



    return 0;


}