题目背景

$Genotype$ 是一个独特的基因串。

题目描述

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

规定一种「分裂」规则，由三个大写字母 $𝐴_1𝐴_2𝐴_3$ 组成，代表 $𝐴_1$ 可以「分裂」为 $𝐴_2𝐴_3$。

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

输入格式

第一行一个整数 $𝑛$ 代表「分裂」规则数。

接下来 $𝑛$ 行每行三个大写字母 $𝐴_1,𝐴_2,𝐴_3$ 代表一个「分裂」规则。

接下来一行一个整数 $𝑘$ 代表给定的 $Genotype$ 数。

接下来 $𝑘$ 行每行若干个大写字母表示一个 $Genotype$。

输出格式

$k$ 行：

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

样例

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

3
1
NIE

数据范围

对于 $100\%$ 的数据，$1≤𝑛≤2000$，$1≤k≤20$，$Genotype$ 的长度最大为 $100$。