Genotypes

A genotype is a finite sequence of genes. It can be written as a word made of the capital letters A–Z, where different letters stand for different kinds of genes.

A gene can bud and thereby turn into a pair of new genes. These transformations are governed by a finite set of rules. Each budding rule is written as three capital letters $A_1A_2A_3$, meaning that gene $A_1$ may turn into the pair of genes $A_2A_3$.

The letter S denotes a special kind of gene called a supergene. Breeding a genotype starts from a sequence of supergenes and proceeds by repeatedly budding chosen genes according to the rules.

Given a set of budding rules and several genotypes, write a program that, for each genotype, decides whether it can be bred from some finite sequence of supergenes and, if so, reports the minimal number of supergenes in such a sequence.

The first line contains one integer $n$ with $1 \le n \le 10000$. Each of the next $n$ lines contains one budding rule, written as a word of three capital letters A–Z. The second or the third letter of a rule may denote a supergene.

The next line contains one integer $k$ with $1 \le k \le 10000$. Each of the next $k$ lines contains one genotype, a non-empty word of at most $100$ capital letters A–Z.

For the $i$-th genotype print a single line containing either:

• one positive integer, the minimal number of supergenes in a sequence from which that genotype can be bred, or
• the word NIE (Polish for "no") if the genotype cannot be bred at all.