톱니바퀴 (Cog-Wheels)

여동생이 여러 크기의 톱니바퀴가 들어 있는 기계 조립 세트를 새로 받았습니다. 여동생은 다양한 기어비(gear ratio)를 가진 기어를 만들기 시작했는데, 어떤 기어비는 만들기가 꽤 까다롭고 어떤 기어비는 아예 만들 수 없다는 것을 알게 되었습니다. 여동생은 어떤 기어비를 만들 수 있고 어떤 기어비를 만들 수 없는지 알려 주는 프로그램을 원합니다. 그 프로그램을 작성해 주세요.

예를 들어, 세트에 톱니 수가 각각 6, 12, 30인 톱니바퀴가 있다고 합시다. 여동생이 5 : 4의 기어비를 만들고 싶어 한다면, 한 가지 방법은 아래 그림과 같습니다.

그림: 5 : 4의 기어비를 실현하는 톱니바퀴 조합.

이 그림은 5 : 4 기어비로 완성된 기어를 나타냅니다. 톱니바퀴 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$ ($1 \le n \le 20$)이 한 줄에 주어집니다. 다음 줄에는 공백 하나로 구분된 $n$개의 정수 $c_1, \ldots, c_n$이 주어지며, 이들은 세트에 있는 $n$가지 서로 다른 톱니바퀴 크기를 나타냅니다 ($i = 1, \ldots, n$에 대해 $5 \le c_i \le 100$). 세트에는 가장 작은 크기 $c = \min\{c_1, \ldots, c_n\}$인 톱니바퀴가 있으며, 모든 크기 $c_1, \ldots, c_n$은 $c$의 배수라고 가정해도 좋습니다.

사용 가능한 톱니바퀴 설명 다음에는 실현할 기어비 목록이 이어집니다. 먼저 기어비의 개수 $m$이 한 줄에 주어집니다. 이어지는 $m$개의 각 줄에는 공백 하나로 구분된 두 정수 $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.

연속한 시나리오의 출력 사이는 빈 줄 하나로 구분합니다.