#include <iostream>
#include <fstream>

#define MAX_LENGTH 10001

struct perl {
    char c;
    perl* next;
};

void free_memo(struct perl* first) {
    struct perl* copy = first;
    while (first) {
        first = first->next;
        delete copy;
        copy = first;
    }
}

bool found_solution(const char result[MAX_LENGTH], struct perl* first) {
    int i = 0;
    struct perl* copy = first;

    while (copy && result[i++] == copy->c)
        copy = copy->next;
    return !copy;
}

bool is_reachable(const char result[MAX_LENGTH], const int& result_length, struct perl* first, int& perls_number) {
    if (result_length == 1)
        return true;

    if (perls_number > result_length)
        return false;

    if (perls_number == result_length && first && found_solution(result, first)) {
        return true;
    }

    if (!first) {
        auto first_child = new perl;
        first_child->c = 'B';
        first_child->next = nullptr;

        auto second_child = new perl;
        second_child->c = 'C';
        second_child->next = nullptr;
        
        int first_perls_number{ 1 },
            second_perls_number{ 1 };
        bool answer =  is_reachable(result, result_length, first_child, first_perls_number) ||
              is_reachable(result, result_length, second_child, second_perls_number);
       
        free_memo(first_child);
        free_memo(second_child);
        return answer;
    }
    
    int i = 0;
    struct perl* copy = first;
    while (copy && result[i] == copy->c) {
        i++;
        copy = copy->next;
    }
    
    if (!copy)
        return false;
    
    if ('1' <= copy->c && copy->c <= '3')
        return false;

    switch (copy->c) {
        case 'A': {
            copy->c = result[i];
            break;
        }
        case 'B': {
            switch (result[i]) {
                case '1': {
                    copy->c = result[i];
                    char a[] = { 'A', '3', 'A', 'C' };
                    for (const auto& character : a) {
                        auto next = new perl;
                        
                        next->c = character;
                        next->next = copy->next;
                        copy = copy->next = next;
                    }
                    perls_number += 4;
                    break;
                }
                case '2': {
                    copy->c = result[i];
                    auto next = new perl;
                    
                    next->c = 'B';
                    next->next = copy->next;
                    copy->next = next;
                    perls_number++;
                    break;
                }
                default: {
                    return false;
                }
            }
            break;
        }
        case 'C': {
            copy->c = result[i];
            switch (result[i]) {
                case '1': {
                    auto next = new perl;

                    next->c = '2';
                    next->next = copy->next;
                    copy = copy->next = next;

                    next = new perl;
                    next->c = 'A';
                    next->next = copy->next;

                    perls_number += 2;
                    break;
                }
                case '2': {
                    break;
                }
                case '3': {
                    auto next = new perl;

                    next->c = 'B';
                    next->next = copy->next;
                    copy = copy->next = next;

                    next = new perl;
                    next->c = 'C';
                    next->next = copy->next;

                    perls_number += 2;
                    break;
                }
            }
            break;
        }
        default: {
            break;
        }
    }
    return is_reachable(result, result_length, first, perls_number);
}

int main() {
    std::fstream in{}, out{};
    int strings_number{ 0 };

    in.open("perle.in", std::ios::in);
    out.open("perle.out", std::ios::out | std::ios::trunc);

    in >> strings_number;
    while (strings_number--) {
        char perl_string[MAX_LENGTH]{};
        int string_length{ 0 },
            aux{ 0 };

        in >> string_length;
        for (int i = 0; i < string_length; ++i)
            in >> perl_string[i];
        out << is_reachable(perl_string, string_length, nullptr, aux) << '\n';
    }
    in.close();
    out.close();
    return 0;
}