#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 1010
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,a[MAX],L[MAX][MAX],R[MAX][MAX];
int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		for(int i=1;i<=n;++i)a[i]=read();
		for(int i=1;i<=n;++i)L[i][i]=R[i][i]=a[i];
		for(int len=2;len<=n;++len)
			for(int i=1,j=i+len-1;j<=n;++i,++j)
			{
				int x=a[j],l=L[i][j-1],r=R[i][j-1];
				if(x==r)L[i][j]=0;
				else if((x>l&&x>r)||(x<l&&x<r))L[i][j]=x;
				else if(r<x&&x<l)L[i][j]=x-1;
				else L[i][j]=x+1;
				x=a[i],l=L[i+1][j],r=R[i+1][j];
				if(x==l)R[i][j]=0;
				else if((x>l&&x>r)||(x<l&&x<r))R[i][j]=x;
				else if(r<x&&x<l)R[i][j]=x+1;
				else R[i][j]=x-1;
			}
		puts(a[1]==L[2][n]?"0":"1");
	}
}