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

int main()
{   
	int tmp;

	ifstream f("perle.in");
	ofstream g("perle.out");
	int n,i,nrc,j;
	f>>n;
	
	for(i=0;i<n;i++)
	{
		f>>nrc;
		
		queue<char> rezultat;
		bool terminat = false;
		
		for(j=0;j<nrc;j++)
		{
			f>>tmp;
			switch(tmp) {
                case 1:
                    rezultat.push('1');
                    break;
                case 2:
                    rezultat.push('2');
                    break;      
                case 3:
                    rezultat.push('3');
                    break; 
            }             
		}
		
		char start = rezultat.front();
    	queue<char> q;
    	
    	if(nrc == 0) {
            g << 0 << endl;
        }
    	else if(nrc == 1) {
            g << 1 << endl; 
        } 
        else {
            if(start == '1') {
                if(nrc == 3) {
                    q.push('C');
                } else {
                    q.push('B');
                }
            }
            else if(start == '2') {
                q.push('B');
            }
            
            while(rezultat.size() > 0)
            {
                if(q.size() == 0) {
                    g << 0 << endl;
                    break;
                }
                char current_element = q.front();
                q.pop();
                
                char c;
                
                switch(current_element) {
                    case '1': case '2': case '3':
                        if(rezultat.front() != current_element) {
                            terminat = true;
                        } else {
                            rezultat.pop();
                        }
                        break;
                    case 'A':
                        rezultat.pop();
                        break;
                    case 'B':
                        c = rezultat.front();
                        if(c == '2') {
                            rezultat.pop();
                            q.push('B');
                        } else if(c == '1') {
                            rezultat.pop();
                            q.push('A');
                            q.push('3');
                            q.push('A');
                            q.push('C');
                        } else {
                            terminat = true;
                        }
                        break;
                    case 'C':
                        c = rezultat.front();
                        if(c == '2') {
                            rezultat.pop();
                        } else if(c == '1') {
                            rezultat.pop();
                            q.push('2');
                            q.push('A');
                        } else {
                            rezultat.pop();
                            q.push('B');
                            q.push('C');
                        }
                        break;
                }
                if(terminat) {
                    break;
                }
            }
            if(rezultat.size() == 0 && q.size() == 0) {
                g << 1 << endl;
            } else {
                g << 0 << endl;
            }
        }
	}
	
	f.close();
	g.close();
	return 0;
}