313004 - 基因序列

基因是一个有限的基因序列，它是由大写的英文字母A~Z组成，不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A_1A_2A_3表示，含义为基因A_1可以分化成A_2A_3。我们用S代表特种基因，繁殖基因是从特种基因序列开始。根据给定的规则，它由被选择控制规则对基因不断进行繁殖而成。

你需要读入一个定义的规则集和一个想生成的单词序列。对每一个给定的基因，根据给定的分化规则，检查是否它能从某一个确定特种基因序列生成，如果能，找到最小的序列长度。

第一行有一个整数n（1≤n≤10000），下面n每一行为一个分化规则。这些规则都由包含A~Z的三个大写字母组成。

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

有k行，在第i行应写入：一个正整数──需要生成第i个基因的最小长度；或者单词NIE，如果不能生成对应的基因。