#include<bits/stdc++.h>
const int MAXN = 50011;
typedef std::pair<int,int> pii;
typedef long long ll;
typedef std::vector<int> P;
std::map<P,int>f;
int cnt[1<<10];
std::vector<P>seq[2011];
void dfs(P a,P b,int x,int c,int up,int cur)
{
    if(x==a.size())
    {
        if(c!=up)return;
        seq[cur].emplace_back(b);
        return;
    }
    if(c<up)
    {
        for(int k=1;k<=a[x]/2;++k)
        {
            b.emplace_back(k),b.emplace_back(a[x]-k);
            dfs(a,b,x+1,c+1,up,cur);
            b.pop_back(),b.pop_back();
        }
    }
    b.emplace_back(a[x]);
    dfs(a,b,x+1,c,up,cur);
}
bool solve(P a,int dep)
{
    std::sort(a.begin(),a.end());
    if(f.count(a))return f[a];
    if(a.back()==1)return f[a]=0;
    int n=a.size();
    for(int s=1;s<(1<<n);++s)
    {
        if(cnt[s]*2>n)continue;
        seq[dep].clear();
        P b,c;
        for(int i=0;i<n;++i)
            if(!(s&(1<<i)))b.emplace_back(a[i]);
        dfs(b,c,0,0,cnt[s],dep);
        for(auto q:seq[dep])
        {
            // printf("From ");
            // for(auto x:a)printf("%d ",x);
            // printf(" To ");
            // for(auto x:q)printf("%d ",x);
            // puts("");
            if(!solve(q,dep+1))return f[a]=1;
        }
    }
    return f[a]=0;
}

ll a[2011];
int main()
{
    for(int s=1;s<(1<<10);++s)cnt[s]=cnt[s&(s-1)]+1;
    int task;
    scanf("%d",&task);
    while(task--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
        std::sort(a+1,a+n+1);
        bool odd=0,even=0;
        for(int i=1;i<=n;++i)
            if(a[i]&1)odd=1;
            else even=1;
        if(n&1)
        {
            if(odd)
            {
                puts(even?"1":"0");
                continue;
            }
            bool all= a[n]==a[1];
            bool ans=1;
            if(even&&all)ans=0;
            bool flag=1;
            for(int i=1;i<=n;++i)
                if((a[i]-2)%4)flag=0;
            if(flag)ans=0;
            printf("%d\n",ans);
        }
        else
        {
            puts(even?"1":"0");
        }
    }
    return 0;
}