P6701 [POI 1997] Genotype

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，输出这个特定的串的最小长度。

#### 数据规模与约定 对于 $100\%$ 的数据，$1 \le n,k \le 2000$，Genotype 的长度最大为 $100$。