Genotypy są skończonymi łańcuchami genów. Opisujemy je za pomocą słów utworzonych z wielkich liter alfabetu angielskiego A - Z. Różne litery oznaczają różne rodzaje genów. Gen może pączkować - zmieniając się w dwójkę nowych genów. Tymi przemianami rządzi skończony zbiór reguł. Każdą regułę pączkowania można zapisać w postaci trójki wielkich liter A₁A₂A₃ co oznacza, że gen A₁ może się zmienić w dwójkę genów A₂A₃.

Wielką literą S oznaczamy specjalny rodzaj genów zwanych supergenami. Hodowla genotypu rozpoczyna się od łańcucha supergenów i polega na sterowanym pączkowaniu wybranych genów zgodnie z ustalonymi regułami.

Zadanie

• wczytuje z pliku tekstowego GEN.IN skończony zbiór reguł pączkowania genów oraz ciąg słów określających genotypy, jakie należy wyhodować,
• dla każdego z danych genotypów bada, czy można go wyhodować z pewnego skończonego łańcucha supergenów zgodnie z danymi regułami pączkowania i jeśli tak, znajduje minimalną długość takiego łańcucha,
• zapisuje wyniki w pliku tekstowym GEN.OUT.

Wejście

W następnym wierszu jest zapisana jedna liczba całkowita 1 <= k <= 10000. W każdym z k kolejnych wierszy jest zapisany jeden genotyp w postaci niepustego słowa złożonego z co najwyżej 100 liter A - Z.

Wyjście

• jedną liczbę całkowitą dodatnią oznaczającą minimalną długość łańcucha supergenów potrzebnego do wyhodowania i-tego danego genotypu, albo
• jedno słowo NIE, jeśli tego genotypu nie da się wyhodować.

Przykład

6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA

3
1
NIE

Twój program powinien szukać pliku GEN.IN w katalogu bieżącym i tworzyć plik GEN.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę GEN.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku GEN.EXE.