#include <fstream>
#include <cstring>
#include <stack>
#include <queue>

/*
Grammar is:
[0] '*' -> 'A' | 'B' | 'C'
[1] 'A' -> '1' | '2' | '3'
[2] 'B' -> '2B' | '1A3AC'
[3] 'C' -> '2' | '3BC' | '12A'
Note:
'*' is the starting element
*/

const char* const G[4][4] = { {"*","A","B","C"},{"A","1","2","3"},{"B","2B","1A3AC","err"},{"C","2","3BC","12A"} };
const int trans[4] = {3,3,2,3};
//immutable symbols are '1' '2' '3'

int getCharPos(const char* charToExpand)
{
	for(int i=0;i<4;++i)
		if(strcmp(G[i][0],charToExpand) == 0)
			return i;
}

bool canParse(const char *c,int le,int ri,const char *charToExpand)
{
   static std::stack<char> mysta; //must make sure that everytime the function finishes this is back to it's original state
   static std::queue<char> myque;
   static bool fromUp;

   int cnt = 0;
   for(int charPos = getCharPos(charToExpand), i = 1; i <= trans[charPos]; ++i)
   {
      bool failed = false;
      fromUp = false;
      int initSizeSta = mysta.size(), initSizeQue = myque.size();

      for(int j=strlen(G[charPos][i]) - 1; j >= 0 ; --j)
	 if(strchr("ABC",G[charPos][i][j]))
	    myque.push(G[charPos][i][j]);

      for(int offset = 0, j=0;G[charPos][i][j] != '\0' && !failed;++j)
      {
	 if(strchr("123",G[charPos][i][j]))
	 {
	    if(le + offset > ri || G[charPos][i][j] != c[le + offset])
	       failed = true;
	    else //valid so far
	    {
	       mysta.push(G[charPos][i][j]);
	       offset++;
	    }
	 }
	 else
	 {
	    int sizeBefore = mysta.size();
	    const char tmp[2] = {G[charPos][i][j],'\0'};
	    myque.pop();
	    if(!canParse(c,le + offset,ri,tmp))
	    {
	       failed = true;
	    }
	    else
	    {
	       offset += mysta.size() - sizeBefore;
	    }
	 }
      }
      if(!failed)
      {
	 if(myque.empty()) //it's done
	 {
	    if(mysta.size() == ri + 1) //either i am at the end of the call stack
	       cnt++, fromUp = true; 
	    else if(fromUp) cnt++; //or i come from the end of the call stack

	    //revert changes
	    while(initSizeSta != mysta.size())
	       mysta.pop();
	    while(initSizeQue != myque.size())
	       myque.pop();
	 }
	 else cnt++;
      }
      else //revert changes
      {
	 while(initSizeSta != mysta.size())
	    mysta.pop();
	 while(initSizeQue != myque.size())
	    myque.pop();
      }
   }
   if(cnt > 0) fromUp = true;
   return cnt > 0 ? true : false;
}

int main()
{
	std::ifstream f("perle.in");
	std::ofstream g("perle.out");

	int M;
	f >> M;
	while(M --)
	{
		int len;
		f >> len;
		char * c = new char[len + 1];
		for(int i=0;i<len;++i)
			f >> c[i];
		c[len] = '\0';
		g << (canParse(c,0,len - 1,"*") ? '1' : '0') << '\n';
		delete[] c;
	}
	return 0;
}