#include <cstdio>
#define MAX_N 10001
int 
A
[
	MAX_N
]
,
L
;
int
fc
(
 int
 )
 ;
int 
fb
(
 int
 
 k
 )
{
	if
		(
		
		A
		[
			k
		]
	==
		2
		)
        
		return 
		fb
		(
		k
		+
		1
		)
		
		;
    if
		(
		A
		[
			k
		]
	==
		1 
		&&
		
		A
		[
			k
			+
			2
		]
	==
		3
		)
        return 
		fc
		(
		k
		+
		4
		)
		;
    return 
		fc
		(
		k
		+
		1
		)
		;
}

int 
fc
(
 int
 
 k
 )
{
    if
		(
		A
		[
			k
		]
	== 
		2
		)

    {
        if
			(
			k
			== 
			L
			-
			1
			)
            return 
			1
			;
        return 
			fc
			(
			k
			+
			1
			)
			;
    }
    if
		(
		A
		[
			k
		]
	== 
		1 
		&& 
		A
		[
			k
			+
			1
		]
	==
		2
		)

    {
        if
			(
			k
			+
			3
			== 
			L
			)

            return 
			1
			;

        return 
			fc
			(
			k
			+
			3
			)
			;

    }
    if
		(
		A
		[
			k
		]
	==
		3
		)

        return 
		fb
		(
		k
		+
		1
		)
	
		;
    return 
		0
		;
}

void
read
(
 )

{
    L
		=
		0
		;


	char 
		S
		[
			100000
		]
	;
    gets
		(
		S
		)
		;

    int 
		k
		=
		0
		,
		p
		=
		0
		,
		i
		=
		0
		;
    for(
		
		;
	S
		[
			k
		]
	!= 
		' '
		;
	k++
		)
      
		L
		=
		L
		*
		1
		0
		+
		(
		S
		[
			k
		]
	-
		'0'
		)
		;
    for(k++; S[k] != '\n'; k++)
    {
        if(S[k] == ' ')
            A[i++] = p,p=0;
        else
            p = p*10 + (S[k] - '0');
    }

}

int solve()
{
    read();
    if(L == 1)
        return 1;
    if(L == 2)
        return 0;
    if(A[0] == 3)
        return fc(0);
    return fb(0);
}

int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int nrt;
    scanf("%d\n",&nrt);
    for(int i=0; i<nrt; i++)
        printf("%d\n",solve());
}