题目背景

Genotype 是一个独特的基因串。

题目描述

我们可以用大写英文字母 $A-Z$ 来描述 Genotype，每个字母就代表一个基因。

规定一种「分裂」规则，由三个大写字母 $A_1A_2A_3$ 组成，代表 $A_1$ 可以「分裂」为 $A_2A_3$。

现在给定 $n$ 个「分裂」规则和 $k$ 个 Genotype，判断这些 Genotype 是否能从一个特定的 只包含大写字母 $S$ 的 串通过「分裂」规则得到，如果可以的话输出特定的串的长度的最小值，如果不可以的话输出 NIE。

输入格式

第一行一个整数 $n$ 代表「分裂」规则数。
接下来 $n$ 行每行三个大写字母 $A_1,A_2,A_3$ 代表一个「分裂」规则。
接下来一行一个整数 $k$ 代表给定的 Genotype 数。
接下来 $k$ 行每行若干个大写字母表示一个 Genotype。

输出格式

$k$ 行：

• 如果没有特定的串通过「分裂」规则得到这个 Genotype，输出 NIE。
• 如果有特定的串通过「分裂」规则得到这个 Genotype，输出这个特定的串的最小长度。

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

3
1
NIE

提示

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,k \le 2000$，Genotype 的长度最大为 $100$。