组装齿轮问题



譬如，在这个玩具中包含了 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。 -assembled gear problems For example, in the toy contains six teeth, 12 teeth and 30 teeth of the gears, and your brother want to see any more than a speed of the transmission device fools. The following diagram shows a possible options : the use of the transmission program four gears, with the first axis is 30 teeth and 12 teeth, with the second axis is six teeth and 12 teeth. Speed than can be obtained by the following formula : (30 / 12) * (6 / 12) = (5 / 2) * (1 / 2) = 5 / 4 = vow However, Use these three gears, assembly would not be able to speed up the ratio of 1:6 gear. Subject to the fixed gear size (the number of gear teeth), judging by the formation of these gear speed than certain. We assume that the quantity of each gear are sufficient. Importation of importation of the first li