#include <bits/stdc++.h>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

vector <int> E[12];
vector <int> vals[12][12];
bool finals[12];

bool ch(vector <int> &vv, int elem)  {
	for(auto x : vv)
		if(x == elem)
			return 1;
	return 0;
}

bool dfs(vector <int> &v, int cnt, int n, int node)  {
	if(cnt == n + 1)  {
		return finals[node];
	}
	bool ans = 0;
	for(auto x : E[node])  {
		if(ch(vals[node][x], 0))  {
			ans = max(ans, dfs(v, cnt, n, x));
		}
		if(ch(vals[node][x], v[cnt]))  {
			ans = max(ans, dfs(v, cnt + 1, n, x));
		}
	}
	return ans;
}

inline void solve()  {
	int n;
	fin >> n;
	vector <int> v(n + 1);
	for(int i = 1;i <= n;i++)
		fin >> v[i];
	if(n == 1)  {
		fout << "1\n";
		return;
	}
	fout << dfs(v, 1, n, 1) << "\n";
	return;
}

int main()  {
	int n;
	fin >> n;
	E[1].push_back(2);
	E[1].push_back(4);
	E[2].push_back(3);
	E[2].push_back(9);
	E[2].push_back(4);
	E[4].push_back(4);
	E[4].push_back(5);
	E[5].push_back(6);
	E[6].push_back(7);
	E[7].push_back(8);
	E[8].push_back(2);
	E[9].push_back(10);
	E[10].push_back(11);
	finals[11] = 1;
	finals[3] = 1;
	vals[1][2].push_back(0);
	vals[1][4].push_back(0);
	vals[2][3].push_back(2);
	vals[2][4].push_back(0);
	vals[2][4].push_back(3);
	vals[2][9].push_back(1);
	vals[4][4].push_back(2);
	vals[4][5].push_back(1);
	vals[5][6].push_back(1);
	vals[5][6].push_back(2);
	vals[5][6].push_back(3);
	vals[6][7].push_back(3);
	vals[7][8].push_back(1);
	vals[7][8].push_back(2);
	vals[7][8].push_back(3);
	vals[8][2].push_back(0);
	vals[9][10].push_back(2);
	vals[10][11].push_back(1);
	vals[10][11].push_back(2);
	vals[10][11].push_back(3);
	for(int i = 1;i <= n;i++)  {
		solve();
	}
	fin.close();
	fout.close();
	return 0;
}