#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const string file = "perle";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;

int test;

int nextC(string&, int);

int nextB(string &s, int p)
{
    if (p == -1 || p >= s.length())
        return -1;
    while (p < s.length() && s[p] == '2')
        ++p;
    if (p >= s.length() || s[p] == '3')
        return -1;
    if (p+4 >= s.length())
        return -1;
    if (s[p] != '1' && s[p+2] != '3')
        return -1;
    return nextC(s, p+4);
}

int nextC(string &s, int p)
{
    if (p == -1 || p >= s.length())
        return -1;
    if (s[p] == '1'){
        if (p+2 >= s.length())
            return -1;
        if (s[p] == '1' && s[p+1] == '2')
            return p+3;
        return -1;
    }
    if (s[p] == '2')
        return p+1;
    return nextC(s, nextB(s, p+1));
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> test;
    while (test--){
        int n;
        fin >> n;
        string s;
        for (int i = 1; i <= n; ++i){
            int x;
            fin >> x;
            s += char(x+'0');
        }
        if (n == 1 || nextB(s, 0) == n || nextC(s, 0) == n)
            fout << "1\n";
        else fout << "0\n";
    }
    return 0;
}