#include<fstream>
#include<iostream>
using namespace std;

int n,li;
int sir[10010],tr[10010];

int solution()
{int i,ok,k,j,ok1,ok2;
ok2=1;
if(li==1)                          //Perlele de tip A = -1
  {return 1; ok2=0;}                       //Perlele de tip B = -2
else                               //Perlele de tip C = -3
  {if(li==2)
      {return 0; ok2=0;}
   else
     {tr[1]=sir[1];
      if(tr[1]==1)                  //daca sirul incepe cu 1 sunt posibile situatiile B2 sau C3
        {if(li==3)                  //Verificarea daca este posibila inlocuirea cu C3
            {tr[2]=2;
             tr[3]=sir[3];}
         else
            {tr[2]=-1;              //Daca C3 nu este posibila singura varianta ramasa este B2
             tr[3]=3;
             tr[4]=-1;
             tr[5]=-3;
             ok=1;  k=5;
             if(k>li)                    //Verific daca lungimea sirului meu nu este mai mare decat lungimea
                 {return 0;   ok2=0;}         //sirului dat
             else
               while(ok==1)
                     {ok=0;             //Presupun ca elimin toate perlele magice
                      for(i=1;i<=k;i++)
                         if(tr[i]<0)          //Gasesc perla magica
                           {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
                            if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
                              {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
                                  {tr[i]=1;
                                   ok1=0;}
                               if(sir[i]==2)
                                  {tr[i]=2;
                                   ok1=0;}
                               if(sir[i]==3)
                                  {tr[i]=3;
                                   ok1=0;}
                              }
                            if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
                              {ok=1;             //Sigur inlocuiesc cu perla magica
                               if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                                 {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2
                                  for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune
                                      tr[j+1]=tr[j];   //perla magica de tip B
                                  tr[++i]=-2;
                                  k+=1;
                                  i-=1;}
                               if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
                                 {tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1
                                  for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
                                      tr[j+4]=tr[j];        //restul transformarii : A3AC
                                  tr[++i]=-1;              //Se completeaza cu restul transformarii
                                  tr[++i]=3;
                                  tr[++i]=-1;
                                  tr[++i]=-3;
                                  k+=4; i-=4;
                                 }
                               if((sir[i]==3)&&(ok1==1))
                                   {return 0;  ok2=0;
                                    break;}
                              }
                            if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
                              {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                                 {tr[i]=2;                   //Inlocuiesc cu tip 2
                                  ok1=0;}
                               if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
                                 {ok=1;                       //Pun 2 perle magice
                                  tr[i]=3;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : BC
                                  tr[++i]=-2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-3;
                                  k+=2; i-=2;}
                               if((sir[i]==1)&&(ok1==1))
                                 {ok=1;                      //Pun perla magica
                                  tr[i]=1;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : 2A
                                  tr[++i]=2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-1;
                                  k+=2; i-=2;}
                              }
                           }
                     }
            }
        }
     if(tr[1]==2)
       {tr[2]=-2;
        ok=1;  k=2;
        if(k>li)                //Verific daca lungimea sirului meu nu este mai mare decat lungimea
          {return 0;     ok2=0;}       //sirului dat
        else
          while(ok==1)
               {ok=0;             //Presupun ca elimin toate perlele magice
                for(i=1;i<=k;i++)
                    if(tr[i]<0)          //Gasesc perla magica
                      {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
                       if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
                         {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
                            {tr[i]=1;
                             ok1=0;}
                          if(sir[i]==2)
                            {tr[i]=2;
                             ok1=0;}
                          if(sir[i]==3)
                            {tr[i]=3;
                             ok1=0;}
                         }
                       if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
                         {ok=1;             //Sigur inlocuiesc cu perla magica
                          if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                            {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2
                             for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune
                                 tr[j+1]=tr[j];   //perla magica de tip B
                             tr[++i]=-2;
                             k+=1; i-=1;}
                          if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
                            {tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1
                             for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
                                tr[j+4]=tr[j];        //restul transformarii : A3AC
                             tr[++i]=-1;              //Se completeaza cu restul transformarii
                             tr[++i]=3;
                             tr[++i]=-1;
                             tr[++i]=-3;
                             k+=4; i-=4;
                            }
                          if((sir[i]==3)&&(ok1==1))
                             {return 0;  ok2=0;
                              break;}
                             }
                       if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
                         {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                             {tr[i]=2;                   //Inlocuiesc cu tip 2
                              ok1=0;}
                              if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
                                 {ok=1;                       //Pun 2 perle magice
                                  tr[i]=3;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : BC
                                  tr[++i]=-2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-3;
                                  k+=2; i-=2;}
                               if((sir[i]==1)&&(ok1==1))
                                 {ok=1;                      //Pun perla magica
                                  tr[i]=1;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : 2A
                                  tr[++i]=2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-1;
                                  k+=2; i-=2;}
                         }
                      }
               }
       }
     if(tr[1]==3)
       {tr[2]=-2;
        tr[3]=-3;
        ok=1;  k=3;
        if(k>li)                //Verific daca lungimea sirului meu nu este mai mare decat lungimea
          {return 0; ok2=0;}           //sirului dat
        else
          while(ok==1)
               {ok=0;             //Presupun ca elimin toate perlele magice
                for(i=1;i<=k;i++)
                    if(tr[i]<0)          //Gasesc perla magica
                      {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
                       if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
                         {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
                            {tr[i]=1;
                             ok1=0;}
                          if(sir[i]==2)
                            {tr[i]=2;
                             ok1=0;}
                          if(sir[i]==3)
                            {tr[i]=3;
                             ok1=0;}
                         }
                       if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
                         {ok=1;             //Sigur inlocuiesc cu perla magica
                          if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                            {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2
                             for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune
                                 tr[j+1]=tr[j];   //perla magica de tip B
                             tr[++i]=-2;
                             k+=1; i-=1;}
                          if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
                            {tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1
                             for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
                                tr[j+4]=tr[j];        //restul transformarii : A3AC
                             tr[++i]=-1;              //Se completeaza cu restul transformarii
                             tr[++i]=3;
                             tr[++i]=-1;
                             tr[++i]=-3;
                             k+=4; i-=4;
                            }
                          if((sir[i]==3)&&(ok1==1))
                             {return 0; ok2=0;
                              break;}
                             }
                       if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
                         {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
                             {tr[i]=2;                   //Inlocuiesc cu tip 2
                              ok1=0;}
                              if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
                                 {ok=1;                       //Pun 2 perle magice
                                  tr[i]=3;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : BC
                                  tr[++i]=-2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-3;
                                  k+=2; i-=2;}
                               if((sir[i]==1)&&(ok1==1))
                                 {ok=1;                      //Pun perla magica
                                  tr[i]=1;
                                  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
                                     tr[j+2]=tr[j];          //restul transformarii : 2A
                                  tr[++i]=2;                //Se completeaza cu restul transformarii
                                  tr[++i]=-1;
                                  k+=2; i-=2;}
                         }
                      }
               }
       }
     }
  }
if(ok2==1)
  {ok=1;
   if(k>li)
     return 0;
   else
     {for(i=1;((i<=k)&&(ok==1));i++)
        if(tr[i]!=sir[i])
          ok=0;
      return ok;}
  }
}

int main()
{int q,i,r;
ifstream g("perle.in");
ofstream t("perle.out");
g>>n;
for(q=1;q<=n;q++)
   {g>>li;
    for(i=1;i<=li;i++)
        g>>sir[i];
    r=solution();
    t<<r<<"\n";}
g.close();
t.close();
return 0;
}