#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000 + 5;
char c[74];
int n, k, dp[74][74][27], g[74], a[maxn][3];

void read() {
    scanf("%d", &n);
    char x, y, z;
    for (int i = 1; i <= n; ++ i) {
        scanf(" %c %c %c", &x, &y, &z);
        a[i][0] = x - 'A', a[i][1] = y - 'A', a[i][2] = z - 'A';
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; ++ i) {
        memset(dp, 0, sizeof dp);
        scanf("%s", c + 1);
        int len = strlen(c + 1);
        for (int i = 1; i <= len; ++ i) dp[i][i][c[i] - 'A'] = 1;
        for (int d = 2; d <= len; ++ d)
            for (int l = 1, r; (r = l + d - 1) <= len; ++ l)
                for (int k = l; k < r; ++ k)
                    for (int j = 1; j <= n; ++ j)
                        dp[l][r][a[j][0]] = max(dp[l][r][a[j][0]], dp[l][k][a[j][1]] & dp[k + 1][r][a[j][2]]);
        memset(g, 0x3f, sizeof g);
        dp[0][0][18] = 1;
        g[0] = 0;
        for (int r = 1; r <= len; ++ r)
            for (int l = 0; l < r; ++ l)
                if (dp[l + 1][r][18]) g[r] = min(g[r], g[l] + 1);
        if (g[len] == 1061109567) printf("NIE\n");
        else printf("%d\n", g[len]);
    }
}

int main() {
    read();
    return 0;
}

对于第26行的取 $max$ 我们把它换成位运算； dp[l][r][a[j][0]] |= dp[l][k][a[j][1]] & dp[k + 1][r][a[j][2]];