Cog-Wheels

Your little sister has just got a new mechanical building kit that includes many cog-wheels of different sizes. She starts building gears with different ratios, but soon notices that some ratios are quite difficult to realize, and some others she cannot realize at all. She would like a computer program that tells her which ratios can be realized and which cannot. She asks you to write that program.

For example, suppose the kit contains cog-wheels with 6, 12, and 30 cogs, and she wants to realize a gear of ratio 5 : 4. One possible solution is shown below.

Figure: A combination of cog-wheels realizing a gear of 5 : 4.

It shows a complete gear of ratio 5 : 4. Four wheels are used: cog-wheels of sizes 30 and 12 on the first axis, and cog-wheels of sizes 6 and 12 on the second axis. The gear ratio is

$$\frac{30}{12} \cdot \frac{6}{12} = \frac{5}{2} \cdot \frac{1}{2} = \frac{5}{4} = 5 : 4$$

as desired. In contrast, a gear of ratio 1 : 6 cannot be realized with the cog-wheels she has.

Given the sizes of the cog-wheels in the kit (that is, the number of cogs they have), decide whether a given gear ratio can be built. You may use any finite number of cog-wheels of each available size.

The input begins with a line containing the number of scenarios.

Each scenario starts with a description of the cog-wheels in the kit. First, a line contains the number $n$ of different cog-wheel sizes ($1 \le n \le 20$). The next line contains $n$ integers $c_1, \ldots, c_n$, separated by single blanks; these are the $n$ different cog-wheel sizes in the kit, with $5 \le c_i \le 100$ for $i = 1, \ldots, n$. You may assume that the kit contains a cog-wheel of the smallest size $c = \min{c_1, \ldots, c_n}$ such that every size $c_1, \ldots, c_n$ is a multiple of $c$.

The description of the available cog-wheels is followed by the list of gear ratios to realize. It starts with a line containing the number $m$ of ratios. Each of the next $m$ lines contains two integers $a$ and $b$, separated by a single blank, denoting the ratio $a : b$, with $1 \le a, b \le 10000$.

For every scenario, the output begins with a line containing "Scenario #i:", where i is the scenario number starting at 1. Then, for each gear ratio given in that scenario, print the result. For each gear ratio $a : b$, print a line containing either

Gear ratio a:b can be realized.

or

Gear ratio a:b cannot be realized.

Separate the output of consecutive scenarios with a blank line.