#include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int T;

 int n;

 int a[];

 int lft[][],rht[][];

 //[l,r]区间左侧加/右某个元素使得成为必败态

 int main()

 {

     int i,l,r,t1,t2,x;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(i=;i<=n;++i)

             scanf("%d",a+i);

         if(n==)

         {

             printf("%d\n",);

             continue;

         }

         if(n==)

         {

             printf("%d\n",int(a[]!=a[]));

             continue;

         }

         for(i=;i<=n;++i)

             lft[i][i]=rht[i][i]=a[i];

         for(i=;i<=n;++i)

         {

             for(l=;l<=n-i+;++l)

             {

                 r=l+i-;

                 t1=lft[l][r-];t2=rht[l][r-];x=a[r];

                 if(t2==x)    lft[l][r]=;

                 else if(x<t1&&x<t2)    lft[l][r]=x;

                 else if(x>t1&&x>t2)    lft[l][r]=x;

                 else if(t1<=x&&x<t2)    lft[l][r]=x+;

                 else if(t2<x&&x<=t1)    lft[l][r]=x-;

             }

             for(l=;l<=n-i+;++l)

             {

                 r=l+i-;

                 t1=lft[l+][r];t2=rht[l+][r];x=a[l];

                 if(t1==x)    rht[l][r]=;

                 else if(x<t1&&x<t2)    rht[l][r]=x;

                 else if(x>t1&&x>t2)    rht[l][r]=x;

                 else if(t2<=x&&x<t1)    rht[l][r]=x+;

                 else if(t1<x&&x<=t2)    rht[l][r]=x-;

             }

         }

         printf("%d\n",int(lft[][n]!=a[]));

     }

     return ;

 }