Cog-Wheels

Your younger sister has a mechanical construction kit containing many cog-wheels of different sizes. She likes building gear trains with various transmission ratios, but some ratios are hard to achieve and others are impossible. For each requested ratio, decide whether it can be realized with the wheels in the kit.

A transmission connects two meshing wheels and is written c:d, where c and d are the numbers of cogs of the two wheels. A gear train is a chain of transmissions

$c_1:d_1 \;\; c_2:d_2 \;\; \dots \;\; c_m:d_m$

in which the second wheel of each transmission shares an axis with the first wheel of the next one (wheel $d_i$ and wheel $c_{i+1}$ are on the same axis, for $1 \le i < m$). If the first wheel turns once, the last wheel turns

$\prod_{i=1}^{m} \frac{c_i}{d_i}$

times, and this product is the ratio realized by the train.

For example, with wheels of 6, 12, and 30 cogs, the ratio $4:5$ can be realized by the train 12:30 12:6, because $\frac{12}{30}\cdot\frac{12}{6}=\frac{4}{5}$. In contrast, the ratio $1:6$ cannot be realized with those wheels.

You have an unlimited supply of wheels of each size, and you may use any number of transmissions. Given the available wheel sizes and a target ratio $a:b$, decide whether some gear train realizes exactly that ratio.

The input contains several sets of cog-wheels, each followed by a list of ratios to test.

Each set begins with a line whose first number is $n$ ($1 \le n \le 20$), the number of distinct wheel sizes, followed by the $n$ sizes $a_1, \dots, a_n$. Every wheel has between 5 and 100 cogs, and the number of cogs on every wheel is divisible by the number of cogs on the smallest wheel of that set. You have an infinite supply of each size.

After the sizes comes the list of ratios. Each ratio is a line with two integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le 10000$, $a_j \ne b_j$), meaning the ratio $a_j : b_j$. A line 0 0 ends the list of ratios for the current set.

After the last set, a line containing a single 0 (in place of a wheel count) ends the input.

For each set of cog-wheels, output a section. Begin the section with a line Set #k, where $k$ is the 1-based number of the set.

Then, for each requested ratio (in input order), output one line. If the ratio $a_j : b_j$ can be realized with the wheels of that set, output

Ratio aj:bj: Possible

otherwise output

Ratio aj:bj: Impossible

Here $a_j$ and $b_j$ are the numbers exactly as given in the input.

Print one blank line after every section.