Jack of All Trades

Jack loves to barter: he will trade anything for anything as long as he comes out ahead. Right now he wants to acquire one kind of item and is willing to pay in another kind of item, possibly through a chain of intermediate trades with his friends.

Each friend offers a one-directional trade: a fixed amount of one item in exchange for a fixed amount of another item. A friend willing to give $a_1$ units of name1 in exchange for $a_2$ units of name2 does not necessarily make the reverse trade.

To keep things manageable, Jack never involves more than $9$ other people in a single chain of transactions, so a chain consists of at most $9$ trades.

The exchange ratio of a chain is the number of units of the item Jack is willing to trade that he must give up in order to obtain one unit of the item he wants. Among all chains that convert the item Jack is willing to trade into the item he wants, find the best (smallest) achievable ratio, and the number of distinct chains that achieve exactly that ratio.

The first line contains an integer $n$, the number of test cases.

Each test case begins with a line containing two item names followed by a positive integer $m$ ($m \le 50$): the first name is the item Jack wants, the second name is the item Jack is willing to trade, and $m$ is the number of available trades. Each of the next $m$ lines has the form

a1 name1 a2 name2

meaning that some friend is willing to give $a_1$ units of item name1 in exchange for $a_2$ units of item name2 (the friend gives name1 and receives name2; the reverse trade is not implied). Each of $a_1$ and $a_2$ is a positive integer at most $20$. No trade ever requires more than $2^{31}-1$ items to complete.

For each test case, print Case i: (where $i$ is the case number, starting at $1$), followed by a space, the best ratio Jack can obtain, a single space, and the number of distinct ways Jack could obtain that ratio.

The ratio is written in ordinary decimal (fixed-point) notation, never in scientific notation, rounded to $5$ significant digits with trailing zeros kept, exactly as in the examples (e.g. 1.8000, 0.28571). A value lying exactly halfway between two $5$-significant-digit results is rounded up.