#include <fstream>
#include <string.h>

using namespace std;

ifstream f("perle.in");
ofstream g("perle.out");

long long q, n, Lg[10005];
char sol[10005], B1[5] = "2B", B2[10] = "1A3AC";
char C2[5] = "3BC", C3[5] = "12A", C1[5] = "2";

int main()
{
    f >> q;
    for(long long i = 1; i <= q; i ++)
    {
        f >> n; bool ok = true;
        for(long long j = 1; j <= n; j ++)
            f >> Lg[j];

        if(n == 1){
            g << 1 << '\n';
            continue;
        }

        if(Lg[1] == 1){
            if(n == 3)
                strcpy(sol, C3);
            else
                strcpy(sol, B2);
        }

        else if(Lg[1] == 2)
            strcpy(sol, B1);

        else
            strcpy(sol, C2);

        for(long long j = 2; j <= n; j ++)
        {
            if(isalpha(sol[j - 1]))
            {
                if(sol[j - 1] == 'A')
                    sol[j - 1] = (char)(Lg[j] + 48);

                else if(sol[j - 1] == 'B')
                {
                    char cop[10005];
                    if(sol[j] != 0)
                        strcpy(cop, sol + j);

                    sol[j - 1] = 0;

                    if(Lg[j] == 1)
                        strcat(sol, B2);

                    else if(Lg[j] == 2)
                        strcat(sol, B1);

                    else{
                        g << 0 << '\n';
                        ok = false; break;
                    }

                    strcat(sol, cop);
                }

                else
                {
                    char cop[10005];
                    if(sol[j] != 0)
                        strcpy(cop, sol + j);
                    sol[j - 1] = 0;

                    if(Lg[j] == 1)
                        strcat(sol, C3);

                    else if(Lg[j] == 2)
                        strcat(sol, C1);

                    else
                        strcat(sol, C2);

                    strcat(sol, cop);
                }
            }

            else if(sol[j - 1] - '0' != Lg[j])
            {
                g << 0 << '\n';
                ok = false; break;
            }
        }

        if(ok == true)
        {
            if(strlen(sol) != n)
                g << 0 << '\n';
            else
                g << 1 << '\n';
        }
    }
    return 0;
}