Worms

Biologists are studying an interesting kind of worm. Each worm is a line of cells of various types, and a newborn worm consists of a single cell. In the ordinary kind of worm, exactly one cell of the whole worm grows each day and splits into two cells, so the worm's age in days is one less than its number of cells.

A cell does not split into two arbitrary cells: each worm has a set of growth rules encoded in its DNA. A growth rule is written A→BC, where A, B, and C are uppercase letters from A to T denoting cell types. It means that in one day a single cell A may grow into the two adjacent cells B then C, in that order. The rule I→JK differs from I→KJ. Different worms may have different rule sets.

Some worms have now mutated. A mutated worm behaves exactly like the ordinary kind, except that on a single day any nonempty subset of its cells (at least one, at most all) may grow simultaneously; each growing cell splits into exactly two cells according to the rules.

Because of this, a mutated worm's age can no longer be read off from its length, and some ages cannot be determined uniquely. For example, with the rules A→BC, B→AC, C→AB and current structure ACAB, the worm could be 2 or 3 days old (A → BC → ACAB, or A → BC → ACC → ACAB). Your task is to find the youngest possible age of a given mutated worm.

The input contains several worms. Each worm's data set begins with an integer $N$ ($1 \le N \le 80$), the number of growth rules. Each of the next $N$ lines contains exactly 3 uppercase letters (from A to T) describing one rule: the line

ABC

means that A→BC is a growth rule for this worm (the first cell may grow into the second and third cells, in that order).

The last line of each data set is a string of uppercase letters (from A to T) giving the worm's current cell structure. Every worm has at least 1 and at most 50 cells. The last worm is followed by a line containing a single 0.

For each worm, if it can be grown into the given cell structure under its rule set starting from some single cell, print the minimum possible age of the worm in days, as an integer on its own line. If it cannot be grown into that structure from any single starting cell, print -1 on its own line instead. Print no blank lines between outputs.