背景

你的小妹妹得到了一套新的机械搭建套件，其中包含许多不同尺寸的齿轮。她开始用这些齿轮搭建不同传动比的装置，但很快发现有些传动比很难实现，甚至根本无法实现。她希望你能写一个程序，告诉她哪些传动比可以实现，哪些不能。

例如，假设套件中包含齿数为 6、12 和 30 的齿轮。你妹妹想实现一个 5:4 的传动比。一个可能的解决方案如图 2 所示。

图中展示了一个完整的 5:4 传动比装置。共使用了四个齿轮：第一根轴上是 30 齿和 12 齿的齿轮，第二根轴上是 6 齿和 12 齿的齿轮。传动比由下式给出：

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

这正是我们想要的。然而，使用你妹妹现有的齿轮，无法实现 1:6 的传动比。

问题

给定套件中齿轮的尺寸（即它们的齿数），判断给定的传动比是否可以实现。你可以使用任意数量的每种尺寸的齿轮。

---

输入

输入以一行开始，该行包含场景的数量。

每个场景的输入首先描述套件中的齿轮。第一行包含一个整数 n，表示套件中有 n 种不同尺寸的齿轮（$1 \le n \le 20$）。下一行包含 n 个数字 $c_1, ..., c_n$，用单个空格分隔。这些数字代表套件中 n 种不同尺寸的齿轮，对于 $i = 1, ..., n$，满足 $5 \le c_i \le 100$。你可以假设套件中最小尺寸的齿轮为 $c = \min\{c_1, ..., c_n\}$，并且所有尺寸 $c_1, ..., c_n$ 都是 c 的倍数。

描述可用齿轮的行之后，是待实现的传动比列表。它以一行开始，该行包含传动比的数量。接下来的每一行包含两个整数 a 和 b，用单个空格分隔。它们表示传动比 a:b，其中 $1 \le a, b \le 10000$。

---

输出

每个场景的输出以一行开始，该行包含 "Scenario #i:"，其中 i 是从 1 开始的场景编号。然后打印该场景中所有给定传动比的结果。对于每个传动比 a:b，打印一行，内容为：

Gear ratio a:b can be realized.

或

Gear ratio a:b cannot be realized.

每个场景的输出以一个空行结束。

---

样例输入

2
3
6 12 30
2
5 4
1 6
2
42
2
13 13
42 1

样例输出

Scenario #1:
Gear ratio 5:4 can be realized.
Gear ratio 1:6 cannot be realized.

Scenario #2:
Gear ratio 13:13 can be realized.
Gear ratio 42:1 cannot be realized.

---

来源

Northwestern Europe 2001

题目描述

Yeknom工作努力受到上司的赏识，作为奖赏上司奖励给Yeknom一个装有很多不同尺 寸的齿轮的工具箱。这样Yeknom就不用天天无所事事而可以尝试用不同的齿轮进行组合去 拼装不同的齿轮比了。 但是渐渐地，聪明的Yeknom发现不是所有的比例都是那么容易拼装出来的。有一些比 例甚至永远都无法拼装出来。于是Yeknom想知道给定一些特定的齿轮种类能否拼出 Yeknom想要的齿轮比例。 对于给定的一系列齿轮的种类（齿轮的种类仅由其齿的个数唯一确定） 和一系列给定比例。问是否有拼装方案满足比例。

输入格式

第一行：k表示数据组数。 对于每一组数据： 第一行一个整数n，表示齿轮的种数。 第二行n个整数，表示每种齿轮的齿数。 第三行一个整数m，表示比例数。 接下来m行每行两个数u，v，表示想要的比例为u:v。

输出格式

对于每一组数据： 第一行输出 Scenario #A: 表示为第A组数据，接着对应每一个比例u:v，如果可以拼装成功，输出 Gear ratio u:v can be realized. 否则 Gear ratio u:v cannot be realized. 每一组数据之间有一行空行。

2
3
6 12 30
2
5 4
1 6
1
42
2
13 13
42 1 

提示

K< =100 对于每组数据 N< =100 M< =100 对于每组齿轮种类c1,c2,c3... ,ci<=100 你可以假定存在c=min{c1,c2,...,cn} ,使得c1|c,c2|c...cn|c 对于每个比例u:v,u<=10000,v<=10000 对于一个由两个齿轮组成的单位齿轮组，组成的比例是i:j其中i,j是两种齿轮的齿数。 对于两个齿轮组相连接而成的齿轮组，组成的比例是两个齿轮组比例的乘积。

题目来源

Northwestern Europe 2001