Description

We can use uppercase English letters $A-Z$ to describe a Genotype, where each letter represents a gene.

Define a "split" rule as a triple of uppercase letters $A_1A_2A_3$, meaning $A_1$ can "split" into $A_2A_3$.

Given $n$ "split" rules and $k$ Genotypes, determine whether each Genotype can be obtained from a specific string that consists only of the uppercase letter $S$ by applying the "split" rules. If it is possible, output the minimal length of that specific string; otherwise, output NIE.

Input Format

The first line contains an integer $n$, the number of "split" rules.
Each of the next $n$ lines contains three uppercase letters $A_1,A_2,A_3$ representing one "split" rule.
The next line contains an integer $k$, the number of given Genotypes.
Each of the next $k$ lines contains a string of uppercase letters representing a Genotype.

Output Format

$k$ lines:

• If no such specific string can produce the Genotype via the "split" rules, output NIE.
• If there is such a specific string, output the minimal length of that specific string.

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

3
1
NIE

Hint

Constraints

For $100\%$ of the testdata, $1 \le n,k \le 2000$, and the maximum length of a Genotype is $100$.

Translated by ChatGPT 5