#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

int l;
char c[10002];
int main()
{
    int n, i, j, gasit;
    f>>n;
    for (i=1;i<=n;i++)  {
        f>>l;
        for (j=1;j<=l;j++)
            f>>c[j];
            gasit = 1;
            /*A -> 1  | 2     | 3
B -> 2B | 1A3AC
C -> 2  | 3BC   | 12A
*/
            while (l!=1 && gasit ==1)   {
                if (c[l] == '1')
                    c[l] = 'A';
                else if (c[l] == '3')
                        c[l] = 'A';
                else if (c[l] == '2')   {
                        if (c[l-2] == '3' && c[l-4] == '1') {//1A3AC
                            c[l-4] = 'B';
                            l=l-4;
                        }
                        else
                            c[l] = 'A';
                }
                else if (c[l] == 'A' && c[l-1] == '2' && c[l-2] == '1')//12A
                {
                        c[l-2] = 'C';
                        l=l-2;
                }
                else if (c[l] == 'B' && c[l-1] == '2')//2B
                {
                        c[l-1] = 'B';
                        l=l-1;
                }
                else if (c[l] == 'C' && c[l-1] == 'B' && c[l-2] == '3')//3BC
                {
                        c[l-2] = 'C';
                        l=l-2;
                }
                else if (c[l] == 'C' && c[l-1] == 'B' && c[l-2] == '2')
                {
                        c[l-2] = 'B';
                        c[l-1] = 'C';
                        l=l-1;
                }
                else if (c[l] == 'C' && c[l-2] == '3' && c[l-4] == '1')
                {
                        c[l-4] = 'B';
                        l=l-4;
                }
                else
                    gasit=0;
            }
            g<<gasit<<endl;
    }


    return 0;
}