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

using namespace std;

ifstream cin ("perle.in");
ofstream cout ("perle.out");

const int N = 1e4 + 1;
int a[N + 1];

int n, t;

int main()
{
    for (cin >> t; t && cin >> n; --t)
    {
        memset (a, 0, sizeof(a));
        for (int i = 1; i <= n; ++i)cin >> a[i];
        if (n == 3 && a[1] == 1 && a[2] == 2)cout << "1\n";
        else
        {
            if (n == 1)
                cout << "1\n";
            else
            {
                int j = 1, nrc = 0;
                bool ok  = true;
                if (a[j] == 3)++j;
                while (!(a[j] ^ 2))++j;
                if (a[j] != 1)
                    ok = false, cout << "0\n";
                else
                {
                    ++nrc;
                    ++++j;
                    if (a[j] != 3)
                        ok = false, cout << "0\n";
                    else
                    {
                        ++++j;
                        if (j > n)
                            ok = false, cout << "0\n";
                        else
                        {
                            while (j < n)
                            {
                                if (a[j] == 3)
                                {
                                    ++nrc;
                                    ++j;
                                    while (!(a[j] ^ 2))++j;
                                    if (a[j] != 1)
                                    {
                                        ok = false;
                                        cout << "0\n";
                                        break;
                                    }
                                    ++++j;
                                    if (j > n || a[j] != 3)
                                    {
                                        ok = false;
                                        cout << "0\n";
                                        break;
                                    }
                                    ++++j;
                                    if (j > n)
                                    {
                                        ok = false;
                                        cout << "0\n";
                                        break;
                                    }
                                }
                                else
                                    break;
                            }
                            while (j < n)
                            {
                                if (a[j] == 2)
                                    --nrc, ++j;
                                else
                                {
                                    if (a[j] == 1 && a[j + 1] == 2)
                                        --nrc;
                                    else
                                    {
                                        ok = false;
                                        cout << "0\n";
                                        break;
                                    }
                                    ++++j;
                                    ++j;
                                    if (j > n + 1)
                                    {
                                        ok = false;
                                        cout << "0\n";
                                        break;
                                    }

                                }
                            }
                            if (ok && !nrc)
                                cout << "1\n";

                        }
                    }

                }

            }
        }
    }
    return 0;
}