#include <iostream>
#include <fstream>

using namespace std;

#define MAX 10020

short arr[MAX];
int S;

int test(int k, int T)
{   
    
    //cout << ".." << k << " "  << T << "\n";
    
    switch (T)
    {
       case 4: 
            return k+1; 
            break;
       case 5:
            if (arr[k] == 2 && k+1 != S)
               return test(k+1, 5); else 
            if (arr[k] == 1 && arr[k+2] == 3 && k+4 < S)
               return test(k+4, 6);
            else return -1; //We've got trouble here
            break;
       case 6:
            if (arr[k] == 2) return k+1; else
            if (arr[k] == 1 && arr[k+1] == 2 && k+2 < S)
               return test(k+2, 4); else
            if (arr[k] == 3 && k+2 < S)
            {
               return test( test(k+1, 5), 6);
            }
            break;
       default : return -1;
    }
}

int main(){
    
    ifstream in;
    ofstream out;
    
    int N, i, j, k;
    long long sol = 0;
    
    in.open("perle.in");    
    out.open("perle.out");    
    
    in >> N;
    
    for (i=0;i<N;i++)
    {
        in >> S;        
        
        for (j=0; j<S; j++)
        {
            in >> arr[j];
        }
        
        //Stupid noise
        arr[S  ] = 9;
        arr[S+1] = 9;
        arr[S+2] = 9;        
        
        if (test(0, 4) == S || 
            test(0, 5) == S || 
            test(0, 6) == S)
            out << 1 << "\n";
        else out << 0 << "\n";        
    }        
    
    in.close();    
    out.close();
    
    return 0;
}