The secret pirate treasure has finally been discovered. Its all pure gold and it must soon be converted to money to be of any use. Now, as Captain Hook was exchanging his gold for US dollars, he found out something interesting:
30g gold gives $300 but the same amount of gold also gives 150 units in x currency which in turn can be traded with 200 units in y currency that make $400!
So, basically different conversion routes yield different value for same gold! There's one problem, though. You are his enemy who doesn't want him to make him high profit. So, suggest him ways of conversion such that he ends up with least possible gain in desired currency by selling 30g of gold.
Also remember, there is a wierd rule here, the currency conversion rates are bidirectional, for eg. if you get 4 units in x currency for $1, the next time you exchange those 4 units for dollars. you get 4*4 = $16!
Input: t [number of testcases <= 100] n [number of currencies (including gold) <= 10] NAME [currency name] p [number of currencies that the above currency(NAME) can be exchanged for] nr conversion_factor [nr - index of a currency connected to NAME except the one already mentioned before (the index of gold is 1)] [conversion_factor (<=50) - the factor of currency coversion from NAME to nr assume them to be positive integers] r [number of ways to find <= 10] NAME' [r lines: NAME' - currency to change the gold into] [empty line separating the tests]
Output: t*r lines containing minimum value of gold in desired currency in each case