#include <bits/stdc++.h>

using namespace std;

const int MAXN = 20;
const int MAXLEN = 20;

vector <char> SIGMA;
vector <char> N;
vector <string> p[MAXN];
int S;
int EPS = -1;

void init_grammar() {
    SIGMA.push_back('a');
    SIGMA.push_back('b');
    SIGMA.push_back('c');
    S = 0;
    N.push_back('S');
    N.push_back('A');
    N.push_back('C');
    N.push_back('D');
    p[0].push_back("A");
    p[1].push_back("C");
    p[1].push_back("AC");
    p[2].push_back("cD");
    p[3].push_back("aDb");
    p[3].push_back("");
}

struct situation {
    int v, u;
    size_t pos;
    int i;

    situation(int v, int u, size_t pos, int i): v(v), u(u), pos(pos), i(i) {}

    bool operator < (const situation& b) const {
        return make_pair(make_pair(v, u), make_pair(pos, i)) < make_pair(make_pair(b.v, b.u), make_pair(b.pos, b.i));
    }
};

set <situation> d[MAXLEN];

void scan(const string& w, int j) {
    if (j == 0)
        return;
    for (auto v: d[j - 1]) {
        if (v.pos < p[v.v][v.u].size() && p[v.v][v.u][v.pos] == w[j - 1]) {
            situation to = v;
            ++to.pos;
            d[j].insert(to);
        }
    }
}

void complete(const string& w, size_t j) {
    for (auto v: d[j]) {
        if (v.pos < p[v.v][v.u].size())
            continue;
        int i = v.i;
        for (auto prev: d[i]) {
            if (prev.pos >= p[prev.v][prev.u].size() || p[prev.v][prev.u][prev.pos] != N[v.v])
                continue;
            situation to = prev;
            ++to.pos;
            d[j].insert(to);
        }
    }
}

void predict(const string& w, int j) {
    for (auto v: d[j]) {
        if (v.pos >= p[v.v][v.u].size() || find(N.begin(), N.end(), p[v.v][v.u][v.pos]) == N.end())
            continue;
        int tov = distance(N.begin(), find(N.begin(), N.end(), p[v.v][v.u][v.pos]));
        for (size_t tou = 0; tou < p[tov].size(); ++tou) {
            d[j].insert(situation(tov, tou, 0, j));
        }
    }
}

bool check(string w) {
    for (size_t i = 0; i <= w.size(); ++i) {
        d[i].clear();
    }
    d[0].insert(situation(S, 0, 0, 0));
    for (size_t j = 0; j <= w.size(); ++j) {
        scan(w, j);
        size_t dj_size = -1;
        while (dj_size != d[j].size()) {
            dj_size = d[j].size();
            complete(w, j);
            predict(w, j);
        }
        cout << j << ":" << endl;
        for (auto v: d[j]) {
            cout << N[v.v] << " -> " << p[v.v][v.u] << " " << v.pos << " " << v.i << endl;
        }
    }

    situation ok(S, 0, 1, 0);
    return d[w.size()].count(ok);
}

int main() {
//  freopen("t.in", "r", stdin);
    init_grammar();
    int tests_cnt;
    cin >> tests_cnt;
    for (int test_num = 0; test_num < tests_cnt; ++test_num) {
        string w;
        cin >> w;
        cout << "test #" << test_num << ":\n";
        int fl = check(w);
        cout << "verdict: ";
        if (fl)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}