#include <bits/stdc++.h>
using namespace std;

int i, t, n;
char c[10005];

bool Solve(string s, int poz = 0) {
  if(s.size() > n) return 0;
  if(s.size() == n) {
    bool ok = 1;
    for(int i = 0; i < n; ++i)
      if(s[i] != c[i]) ok = 0, i = n + 1;
    if(ok) return 1;
  }

  for(int i = poz; i < s.size(); ++i) {
    if(s[i] == c[i]) continue;

    if(s[i] >= '1' && s[i] <= '3') return 0;

    if(s[i] == 'A') {
      if(c[i] == '1') return Solve(s.substr(0, i) + "1" + s.substr(i + 1), i);
      if(c[i] == '2') return Solve(s.substr(0, i) + "2" + s.substr(i + 1), i);
      if(c[i] == '3') return Solve(s.substr(0, i) + "3" + s.substr(i + 1), i);
      return 0;
    }

    if(s[i] == 'B') {
      if(c[i] == '1') return Solve(s.substr(0, i) + "1A3AC" + s.substr(i + 1), i);
      if(c[i] == '2') return Solve(s.substr(0, i) + "2B" + s.substr(i + 1), i);
      return 0;
    }

    if(s[i] == 'C') {
      if(c[i] == '1') return Solve(s.substr(0, i) + "12A" + s.substr(i + 1), i);
      if(c[i] == '2') return Solve(s.substr(0, i) + "2" + s.substr(i + 1), i);
      if(c[i] == '3') return Solve(s.substr(0, i) + "3BC" + s.substr(i + 1), i);
      return 0;
    }
  }

  return s.size() == n;
}

int main()
{
  ifstream cin("perle.in");
  ofstream cout("perle.out");
  ios_base::sync_with_stdio(0);

  for(cin >> t; t; --t) {
    cin >> n;
    for(i = 0; i < n; ++i) cin >> c[i];

    if(n == 1) cout << "1\n";
    else if(Solve("A") || Solve("B") || Solve("C")) cout << "1\n";
         else cout << "0\n";
  }

  return 0;
}