Frank Marks works at the Business Oce of a large company. His company has customers all over the world and must deal with many dierent currencies. Employees often come to the Business Oce with requisitions for certain amounts of money, such as \textbf{100 }American dollars or \textbf{452} Euros. If Frank has the cash on hand, he gives the employee exactly what they need; if he does not have enough of the particular currency requested, he substitutes it with another one. This is sometimes dicult because he may have many dierent currencies to choose from and would like to pick the one which allows him to get as close to the original requisition as possible without going under (he must provide at least the value requested). For example, suppose Frank has six dierence currencies - \textbf{A}, \textbf{B}, \textbf{C}, \textbf{D}, \textbf{E} and \textbf{F} - and he is aware of the following exchange rates: \textbf{23 A = 17 B} \textbf{16 C = 29 E} \textbf{5 B = 14 E} \textbf{1 D = 7 F} If a requisition for \textbf{100 A} comes in but Frank has less than \textbf{100 A} available, he can substitute with either \textbf{74 B} (equivalent to about \textbf{100.12 A}), \textbf{115 C} (equivalent to about \textbf{100.72 A}) or \textbf{207 E} (equivalent to about \textbf{100.02 A}). Thus, the best approximation available to him is \textbf{207 E}. Note that Frank does not have enough information to find a relationship between currencies \textbf{A} and \textbf{D} or currencies \textbf{A} and \textbf{F}. Also, Frank only has at most \textbf{100000} units of any one currency in stock, so he could not satisfy a request for \textbf{64000 A} using \textbf{E} currency and would need to use \textbf{73078 C} instead. Determining the ideal substitute currency to use when he has completely run out of the requested currency is time consuming, so Frank would like a program to do the calculations for him. \InputFile Each test case begins with a positive integer \textbf{n} indicating the number of exchange rates. The next \textbf{n} lines will be of the form \textbf{val_1 name_1 = val_2 name_2} where \textbf{name_1} and \textbf{name_2} are the names of two distinct currencies, and \textbf{val_1} and \textbf{val_2} are positive integers ≤ \textbf{30}specifying the ratio between the two currencies. There will be no more than \textbf{8} distinct currency names, and any two currencies will be paired together at most once. Currency names will consist of up to ten alphabetic characters. There will be no inconsistencies in the input (such as \textbf{1A = 2B}, \textbf{1B = 2C} and \textbf{1C = 2A}). Following these \textbf{n} lines will be a single line of the form \textbf{val name} which speci es the amount (a positive integer not exceeding \textbf{100000}) and the name of the currency requested. A line containing \textbf{0} will follow the last test case. \OutputFile For each test case, print the case number and the closest approximation without going under the requested value assuming that Frank does not have any of the requested currency available but is fully in stock of all other currencies. There will be a unique answer for each problem instance.