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

int main()
{   
	int tmp;

	ifstream f("perle.in");
	ofstream g("perle.out");
	int n,i,nrc,j;
	f>>n;
	//1 3 3 2 3 1 3 3 2 2 1 2 2
	for(i=0;i<n;i++)
	{
		f>>nrc;
		
		deque<char> rezultat;
		bool terminat = false;

		for(j=0;j<nrc;j++)
		{
			f>>tmp;

			switch(tmp) {
                case 1:
                    rezultat.push_back('1');
                    break;
                case 2:
                    rezultat.push_back('2');
                    break;      
                case 3:
                    rezultat.push_back('3');
                    break; 
            }             
		}
		
		char start = rezultat.front();
    	deque<char> q;
    	
    	if(nrc == 0) {
            g << 0 << endl;
        }
    	else if(nrc == 1) {
            g << 1 << endl; 
        } 
        else {
            if(start == '1') {
                if(nrc == 3) {
                    q.push_back('C');
                } else {
                    q.push_back('B');
                }
            }
            else if(start == '2') {
                q.push_back('B');
            }
            
            while(rezultat.size() > 0)
            {
                if(q.size() == 0) {
                    g << 0 << endl;
                    break;
                }
                char current_element = q.front();
                q.pop_front();
                
                char c;
                
                switch(current_element) {
                    case '1': case '2': case '3':
                        if(rezultat.front() != current_element) {
                            terminat = true;
                        } else {
                            rezultat.pop_front();
                        }
                        break;
                    case 'A':
                        rezultat.pop_front();
                        break;
                    case 'B':
                        c = rezultat.front();
                        if(c == '2') {
                            rezultat.pop_front();
                            q.push_front('B');
                        } else if(c == '1') {
                            rezultat.pop_front();
                            q.push_front('C');
                            q.push_front('A');
                            q.push_front('3');
                            q.push_front('A');
                        } else {
                            terminat = true;
                        }
                        break;
                    case 'C':
                        c = rezultat.front();
                        if(c == '2') {
                            rezultat.pop_front();
                        } else if(c == '1') {
                            rezultat.pop_front();
                            q.push_front('A');
                            q.push_front('2');
                        } else {
                            rezultat.pop_front();
                            q.push_front('C');
                            q.push_front('B');
                        }
                        break;
                }
                if(terminat) {
                    break;
                }
            }
            if(rezultat.size() == 0 && q.size() == 0) {
                g << 1 << endl;
            } else {
                g << 0 << endl;
            }
        }
	}
	
	f.close();
	g.close();
	return 0;
}