Задачи очного тура личного первенства

A Factor Replacement System (FRS) transforms an input integer to another integer by applying rules. Each rule specifies how a set of prime factors of the input integer are replaced by a second set of prime factors. Consider these rules:

Rule 1: 150 `→` 49 [Note: 150=2*3*52; 49=72]

Rule 2: 2 `→` 1

Rule 1 specifies that if the integer has one factor of two, one factor of three, and two factors of five, then those factors are removed and replaced with two factors of seven. Using this rule, the integer 450 (=2*32*52) becomes 147 (=3*72), but the integer 44 (=22*11) is unaltered. Rule 2 specifies that a factor of two should be removed from the integer. Thus 147 is unaltered by this rule but 44 becomes 22 with one application of the rule.

The FRS rules are ordered. For a given input, the rules are examined in order to find a match. When a match is found, the rule is applied once and the process begins again with the first rule. An FRS halts when no rules can be applied. In the above example, the FRS terminates on input 450 with output value 147 and on input 44 with output 11.

Given the rules of an FRS and several positive integers, produce the result of applying the FRS to each integer. It is guaranteed that the FRS will halt for each input integer.

Each FRS description begins with a line containing a non-negative integer `n` (`n\ ≤\ 15`), the number of rules. The next `n` lines contain the rules. Each rule consists of two positive integers separated by at least one space; the first integer is the left part of the rule and the second integer is the right part of the rule, as described above. The first integer is greater than the second integer. The next line contains a non-negative integer `k`, the number of input integers. Each of the next `k` lines contains a single integer to be input to the FRS. All numbers used in the input file for rules and FRS input values are 32 bit integers.

Your program must stop processing input when it reaches an FRS in which n is zero.

For each data set, output a line indicating the data set number. For each input integer, output a single line containing the input integer and the final FRS value, as shown in the Sample Output. Leave a blank line after the output from different FRS's.

2
150 49
2 1
2
450
44
2
9 4
3 1
1
27
0

FRS #1:
     450 becomes 147
     44 becomes 11

FRS #2:
     27 becomes 4