#include <bits/stdc++.h>

using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int t,n,v[100005],sol[100005];
deque<int> st;
void solve()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    if(n==1)
    {
        fout<<1<<'\n';
        return;
    }
    if(n==2)
    {
        fout<<0<<'\n';
        return;
    }
    if(n==3)
    {
        if(v[1]==1&&v[2]==2)
            fout<<1<<'\n';
        else
            fout<<0<<'\n';
    }
    st.clear();
    if(v[1]==1||v[1]==2)
        st.push_back(-2);
    if(v[1]==3)
        st.push_back(-3);
    int poz=1;
    while(!st.empty()&&poz<=n)
    {
        if(st.front()>0)
        {
            if(st.front()!=v[poz])
            {
                fout<<0<<'\n';
                return;
            }
            st.pop_front();
            poz++;
            continue;
        }
        if(st.front()==-1)
        {
            st.pop_front();
            poz++;
            continue;
        }
        if(st.front()==-2)
        {
            st.pop_front();
            if(v[poz]==2)
            {
                st.push_front(-2);
                poz++;
                continue;
            }
            if(v[poz]==1)
            {
                st.push_front(-3);
                st.push_front(-1);
                st.push_front(3);
                st.push_front(-1);
                poz++;
                continue;
            }
            fout<<0<<'\n';
            return;
        }
        if(st.front()==-3)
        {
            st.pop_front();
            if(v[poz]==2)
            {
                poz++;
                continue;
            }
            if(v[poz]==3)
            {
                st.push_front(-3);
                st.push_front(-2);
                poz++;
                continue;
            }
            if(v[poz]==1)
            {
                st.push_front(-1);
                st.push_front(2);
                poz++;
                continue;
            }
        }
    }
    if(st.empty()&&poz>n)
    {
        fout<<1<<'\n';
        return;
    }
    fout<<0<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>t;
    while(t--)
        solve();
    return 0;
}