龙王恨:求助一C程序，急

你的弟弟买了一套新的玩具，用这套玩具，他可以组装自己的机器。在玩具中有很多不同尺寸的齿轮，开始的时候他可以直接使用齿轮组装不同转速比的传动装置，但后来他发现有些转速比用已有的齿轮就很难组装出来。他希望你给他编写一个电脑程序，帮助他找到组装传动装置的方法。
譬如，在这个玩具中包含了 6 齿、12 齿和 30 齿的齿轮，而你的弟弟希望搞一个转速比为 5:4 的传动装置。下图就显示了一种可能的方案：

这个传动方案使用了四个齿轮，第一跟轴上是 30 齿和 12 齿的，第二跟轴上是 6 齿和 12 齿的。转速比可以通过如下公式获得：
(30 / 12) * (6 / 12) = (5 / 2) * (1 / 2) = 5 / 4 = 5:4
然而，使用以上三种齿轮，就没法组装出转速比为 1:6 的传动装置。
题目
给定齿轮的大小（齿轮有多少个齿），判断通过这些齿轮能否组成一定的转速比。我们假定每种齿轮的数量都足够多。
输入
输入的第一行是一个数字 n，它表示在玩具中有几种齿轮（1 <= n <= 20）。下一行包含了 n 个数字 c1...cn，以空白符隔开，他们表示了玩具中的 n 种齿轮的大小（5 <= ci <= 100，其中 1 <= i <= n）。你可以假定在玩具中所有齿轮的大小都是最小齿轮大小的倍数。
再下一行有一个整数 m，它表示所需的实现的转速比有多少组，而之后的 m 行中每行都有两个整数 a 和 b，它们表示要实现的转速比为 a:b，其中 1 <= a, b <= 10000。
测试用例 1：3
6 12 3
2
5 4
1 6
期待的输出1 Gear ratio 5:4 can be realized.

2 Gear ratio 1:6 cannot be realized.

测试用例 2：1
42
2
13 13
42 1
期待的输出1 Gear ratio 13:13 can be realized.

2 Gear ratio 42:1 cannot be realized.

时间限制 1秒 1秒
内存限制 1024KB 1024KB