벌레

생물학자들이 흥미로운 종류의 벌레를 연구하고 있다. 각 벌레는 여러 종류의 세포가 한 줄로 이어진 형태이며, 갓 태어난 벌레는 세포 하나로 이루어져 있다. 평범한 벌레는 매일 벌레 전체에서 정확히 한 세포가 자라나 두 세포로 갈라지므로, 벌레의 나이(일수)는 세포 수보다 정확히 $1$ 작다.

세포는 아무 두 세포로나 갈라지지 않는다. 각 벌레는 DNA에 담긴 성장 규칙의 집합을 따른다. 성장 규칙은 A→BC처럼 쓰며, 여기서 A, B, C는 세포 종류를 나타내는 A부터 T까지의 대문자이다. 이 규칙은 하루 동안 한 세포 A가 두 개의 이웃한 세포 B, C로 그 순서대로 자라날 수 있음을 뜻한다. 규칙 I→JK와 I→KJ는 서로 다르다. 벌레마다 규칙 집합이 다를 수 있다.

이제 일부 벌레가 돌연변이를 일으켰다. 돌연변이 벌레는 평범한 벌레와 똑같이 행동하되, 하루 동안 세포들 중 비어 있지 않은 임의의 부분집합(적어도 하나, 많으면 전부)이 동시에 자라날 수 있다는 점만 다르다. 자라나는 각 세포는 규칙에 따라 정확히 두 세포로 갈라진다.

이 때문에 돌연변이 벌레의 나이는 더 이상 길이만으로 알 수 없고, 어떤 벌레는 나이를 유일하게 정할 수 없다. 예를 들어 규칙이 A→BC, B→AC, C→AB이고 현재 구조가 ACAB라면, 이 벌레는 $2$일 또는 $3$일 된 것일 수 있다(A → BC → ACAB, 또는 A → BC → ACC → ACAB). 주어진 돌연변이 벌레가 될 수 있는 가장 어린 나이를 구하여라.

입력에는 여러 마리의 벌레가 주어진다. 각 벌레의 데이터는 성장 규칙의 수를 나타내는 정수 $N$ ($1 \le N \le 80$)으로 시작한다. 이어지는 $N$개의 줄에는 각각 정확히 3개의 대문자(A부터 T까지)가 주어져 하나의 규칙을 나타낸다. 예를 들어

ABC

는 이 벌레의 성장 규칙 A→BC를 뜻한다(첫 번째 세포가 두 번째와 세 번째 세포로 그 순서대로 자라날 수 있다).

각 데이터의 마지막 줄은 벌레의 현재 세포 구조를 나타내는 대문자(A부터 T까지) 문자열이다. 모든 벌레의 세포 수는 1개 이상 50개 이하이다. 마지막 벌레 뒤에는 0 하나만 있는 줄이 온다.

각 벌레마다, 그 벌레가 어떤 하나의 세포에서 시작하여 주어진 규칙 집합으로 주어진 세포 구조까지 자라날 수 있으면, 그 벌레가 될 수 있는 최소 나이(일수)를 정수로 한 줄에 출력한다. 어떤 하나의 시작 세포에서도 그 구조까지 자라날 수 없으면, 대신 -1을 한 줄에 출력한다. 출력들 사이에 빈 줄을 넣지 않는다.