题目描述

背景
你的妹妹新买了一套机械积木套装，里面包含多种不同尺寸的齿轮。她开始尝试搭建不同传动比的齿轮组，但很快发现有些传动比难以实现，有些则完全无法实现。她希望有一个计算机程序能告诉她哪些传动比可以实现，哪些不能。于是她请你编写一个程序来完成这个任务。

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

该方案使用了四个齿轮：第一轴上安装$30$齿和$12$齿的齿轮，第二轴上安装$6$齿和$12$齿的齿轮。传动比计算如下：

然而，使用现有的齿轮无法实现$1:6$的传动比。

问题
给定套装中齿轮的尺寸（即齿数），判断给定的传动比能否被实现。你可以使用任意数量的每种尺寸的齿轮。

输入格式

输入以一行整数开始，表示测试场景的数量。

每个测试场景的输入包含：

1. 一行整数$n$，表示不同尺寸齿轮的数量（$1 \leq n \leq 20$）
2. 一行$n$个整数$c_1 \ldots c_n$，用空格分隔，表示套装中的齿轮尺寸（$5 \leq c_i \leq 100$） • 保证套装中存在最小尺寸$c = \min\{c_1, \ldots, c_n\}$，且所有尺寸$c_1, \ldots, c_n$都是$c$的倍数
3. 一行整数$m$，表示需要判断的传动比数量
4. 接下来$m$行，每行两个整数$a$和$b$，用空格分隔，表示传动比$a:b$（$1 \leq a, b \leq 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
1
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.

题目来源

2001年西北欧地区编程竞赛