题目描述

在将要到来的星际战争中,基因武器的杀伤威力极其巨大，因此研究天顶 星人的基因十分必要。魔法学院发现天顶星人的基因是一个有限的基因序列,它 是由大写的英文字母$\red{A\sim Z}$组成,不同的字母表示不同种类的基因。一个基因可 以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的 规则可以用三个大写字母$\red{Al,A2,A3}$表示,合义为基因$\red{Al}$可以分化成$\red{A2,A3,}$ 我们用$\red{S}$代表特种基因,繁殖天顶星人是从特种基因序列开始。根据给定的规则， 它由被选择控制规则对基因不断进行繁殖而成。

你需要从文本文件$\red{GEN.IN}$读入一个定义的规则集和一个想生成的天顶星人 单词序列。对每一个给定的基因,根据给定的分化规则,检查是否它能从某一个确定 特种基因序列生，成,如果能,找到最小的序列长度,将结果写入文本文件$\red{GEN.OUT}$。

输入格式

在文件$\red{GEN.IN}$的第一行有一个整数$\red{n,1≤}$$\red{n≤}$$\red{10 000,}$下面$\red{n}$每一行为一个 分化规则。这些规则都由包含$\red{A\sim Z}$的三个大写字母组成。

接下来有一个整数$\red{k,1≤}$$\red{k≤}$$\red{10000,}$接下来的$\red{k}$行有一个基因序列，基因序列 由没有空格的单词组成。最多$\red{100 }$个英文大写字母。

输出格式

在文件$\red{GEN.OUT}$中有$\red{k}$行,在第$\red{1}$行应写入:一个正整数---- 需要生成第$\red{1}$ 个基因的最小长度;或者单词$\red{NIE,}$如果不能生成对应的基因。

样例

输入样例

6
SAB .
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

输出样例

3
1
NIE