/*
TASK:seq
LANG:C++
*/
#include<iostream>
#include<vector>
using namespace std;

class ch
{
      public:
             long long st;
             int pos;
};

vector<int>q;
vector<ch>p;


void solve()
{
     int i,j;
     int k,z=p.size(),l=0,ls=0;
     for(i=0;i<z-1;i++)
      for(j=i;j<z;j++)
       if(p[i].st>p[j].st){swap(p[i],p[j]);ls=1;}
     if(ls==1)
     {
      z/=2;
      for(k=0;k<z;k++)
      {
       if(p[k].pos%2==0)l=1;
       else l=0;break;
      }
      if(l==1)q.push_back(1);
      else q.push_back(0);
     }
     else q.push_back(1);
}

int main()
{
    long long n,m,i,j,a;ch t;
    cin>>n;
    for(i=0;i<n;i++)
    {
                    cin>>m;
                    for(j=0;j<m;j++)
                    {
                     cin>>a;
                     t.st=a;
                     t.pos=j+1;
                     p.push_back(t);
                    }
                    solve();
                    p.clear();
    }
    for(i=0;i<n;i++)
     cout<<q[i];
    cout<<'\n';
    return 0;
}


