#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) {
    struct perl* copy = first;
    int i = 0;

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

struct perl* make_perl(char data, struct perl* next) {
    auto new_perl = new perl;
    new_perl->c = data;
    new_perl->next = next;
    return new_perl;
}

bool is_reachable(const char result[MAX_LENGTH], const int& result_length, int memo_index, struct perl* first, int& perls_number) {
    if (perls_number > result_length) return false;

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

    if (!first) {                                  /// STARTING THE CHILDREN (B OR C)
        if (result[0] == '3') {                    /// cannot begin with 3 and use 'B' as starting point
            auto c_start_case = make_perl('C', nullptr);

            int c_start_case_perls_number{ 1 };

            bool answer = is_reachable(result, result_length, 0, c_start_case, c_start_case_perls_number);
            free_memo(c_start_case);
            return answer;
        }
        auto first_child = make_perl('B', nullptr);
        auto second_child = make_perl('C', nullptr);
        int first_perls_number{ 1 }, second_perls_number{ 1 };

        bool answer =  is_reachable(result, result_length, 0, first_child, first_perls_number) ||
              is_reachable(result, result_length, 0, second_child, second_perls_number);
       
        free_memo(first_child);
        free_memo(second_child);
        return answer;
    }

    struct perl* copy = first;
    for (int i = 0; i < memo_index; ++i)
        copy = copy->next;
    while (copy && (result[memo_index] == copy->c || copy->c == 'A')) {
        memo_index++;
        copy = copy->next;
    }
    
    if (!copy)
        return false;

    switch (copy->c) {
        case 'B': {
            copy->c = result[memo_index];

//            if (result_length == perls_number)          /// B cannot be converted in one character! (just 2 or 4)
//                return false;

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

                    next = make_perl('A', copy->next);
                    copy->next = next;

                    perls_number += 2;
                    break;
                }
                case '2': {                             /// C -> { 2 }
                    break;
                }
                case '3': {                             /// C -> { 3 B C }
                    auto next = make_perl('B', copy->next);
                    copy = copy->next = next;

                    next = make_perl('C', copy->next);
                    copy->next = next;

                    perls_number += 2;
                    break;
                }
            }
            break;
        }
        default: {
            return false;
        }
    }
    return is_reachable(result, result_length, memo_index, 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 << ((string_length > 1) ? is_reachable(perl_string, string_length, 0, nullptr, aux) : 1) << '\n';
    }
    in.close();
    out.close();
    return 0;
}