Keys

Seungi wants to give half of his pile of keys to Hyebin. A key can be slid along a spiral to be put onto a key ring or taken off it, and two key rings can be joined or separated the same way.

Putting one key onto a ring (or taking it off) counts as one operation, and joining one ring to another (or separating them) also counts as one operation. However, sliding a key on or off is far harder than joining or separating rings (Hyebin does Seungi's nail art, so his nails must not get hurt). Therefore Seungi first minimizes the number of key operations (putting a key on or taking it off); among all the ways that achieve that minimum, he then minimizes the number of ring operations (joining or separating rings).

When everything is done, the keys must be split into exactly two piles: the pile Seungi keeps and the pile he gives to Hyebin. Keys with uppercase letters A through M belong to Seungi, and keys N through Z belong to Hyebin. Each pile must be connected into a single group, and every key must be on exactly one ring. If one of the two people would receive no keys at all, the keys need not be split into two piles. While the operations are performed an empty ring holding no keys may be left over; such a ring is set aside so that it belongs to neither pile.

For example, starting from four keys held on three rings, if Seungi wants to give Hyebin the keys N and R, he can form the two piles with two key operations and one ring operation.

The input consists of several test cases. Each test case is given as several lines of two characters each, followed by a line containing only 0. A lowercase letter denotes a key ring and an uppercase letter denotes a key. The two characters on a line mean either that a key is on a ring (key, ring) or that two rings are joined (ring, ring). The input ends at end of file.

The two characters are never both uppercase. Within a test case the same pair is never given twice. Each key is on exactly one ring, and in the initial state every ring has at least one key on it (a ring may become empty while operations are performed). Every key and every ring that appears is listed at least once.

For each test case, print one line in the form Case x: a b, where x is the test case number starting from 1, a is the minimum number of key operations (putting a key on or taking it off), and b is the minimum number of ring operations (joining or separating rings). If splitting into the two required piles is impossible, print Case x: impossible instead.