#include <bits/stdc++.h>
#define for0(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(s) getline(fin, s)
//#define for1(i,n) for(int i=1; i<=n; i++)
#define FASTIO ios_base::sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAX=100005;
const ull MOD=100003;
const int NR_CIFRE=100005;
/*template <typename T>
string to_string(const T& n){
    ostringstream os;
    os << n;
    return os.str();
}
*/
ifstream fin("perle.in");
ofstream fout("perle.out");

int main()
{

    deque<short> v;
    queue<short> coada; /// 4=A, 5=B, 6=C;
    int n;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        int k;
        fin>>k;
        for(int j=1; j<=k; j++)
        {
            short x;
            fin>>x;
            v.pb(x);
        }
        if(k==1)
        {
            fout<<"1\n";
            v.clear();
        }
        else
        {
            int ans=2;
            if(v.front()==1)
            {
                if(v.size()==3 && v[0]==1 && v[1]==2)
                    ans=1;//cout<<"1\n";
                else
                {
                    if(v.size()<5)
                        ans=0;//cout<<"0\n";
                    else
                    {
                        if(v[2]!=3)
                            ans=0;//cout<<"0\n";
                        else
                        {
                            v.pop_front(); v.pop_front(); v.pop_front(); v.pop_front();
                            coada.push(6);
                        }
                    }
                }
            }
            else if(v.front()==2)
            {
                while(!v.empty() && v.front()==2)
                    v.pop_front();
                if(v.empty())
                    ans=0;//cout<<"0\n";
                else
                    coada.push(5);
            }
            else if(v.front()==3)
            {
                v.pop_front();
                coada.push(5);
                coada.push(6);
            }
            if(ans!=2)
                fout<<ans<<'\n';
            else
            {
                while(!coada.empty())
                {   //cout<<coada.front();
                    if(coada.front()==1)
                    {
                        if(!v.empty() && v.front()==1)
                        {
                            v.pop_front();
                            coada.pop();
                        }
                        else
                        {
                            fout<<"0\n";
                            break;
                        }
                    }
                    else if(coada.front()==2)
                    {
                        if(!v.empty() && v.front()==2)
                        {
                            v.pop_front();
                            coada.pop();
                        }
                        else
                        {
                            fout<<"0\n";
                            break;
                        }
                    }
                    else if(coada.front()==3)
                    {
                        if(!v.empty() && v.front()==3)
                        {
                            v.pop_front();
                            coada.pop();
                        }
                        else
                        {
                            fout<<"0\n";
                            break;
                        }
                    }
                    else if(coada.front()==4)
                    {
                        if(!v.empty())
                        {
                            coada.pop();
                            v.pop_front();
                        }
                        else
                        {
                            fout<<"0\n";
                            break;
                        }
                    }
                    else if(coada.front()==5)
                    {
                        while(!v.empty() && v.front()==2)
                            v.pop_front();
                        if(v.empty())
                        {
                            fout<<"0\n";
                            break;
                        }
                        if(v.front()==1)
                        {
                            //cout<<9;
                            coada.push(1); coada.push(4); coada.push(3); coada.push(4); coada.push(6);
                        }
                        else
                        {
                            fout<<"0\n";
                            break;
                        }
                        coada.pop();
                    }
                    else if(coada.front()==6)
                    {
                        if(v.empty())
                        {
                            fout<<"0\n";
                            break;
                        }
                        if(v.front()==1)
                        {
                            coada.push(1); coada.push(2); coada.push(4);
                        }
                        if(v.front()==2)
                        {
                            coada.push(2);
                        }
                        if(v.front()==3)
                        {
                            coada.push(3); coada.push(5); coada.push(6);
                        }
                        coada.pop();
                    }

                }
                if(coada.empty() && v.empty())
                    fout<<"1\n";
                else
                {
                    if(coada.empty())
                    {
                        fgout<<"0\n";
                        v.clear();
                    }
                    else
                    {
                        while(!coada.empty())
                            coada.pop();
                    }
                }

            }
        }
    }



    return 0;
}