톱니바퀴

여동생이 크기가 서로 다른 톱니바퀴가 잔뜩 들어 있는 기계 조립 세트를 가지고 있습니다. 여동생은 여러 가지 기어비(전동비)를 가진 기어 장치를 만들고 싶어 하지만, 어떤 비율은 만들기 까다롭고 어떤 비율은 아예 만들 수 없습니다. 요청받은 각 비율을 세트에 있는 톱니바퀴로 실제로 만들 수 있는지 판정하세요.

하나의 물림(transmission) 은 서로 맞물린 두 톱니바퀴를 연결하며 c:d 로 표기합니다. 여기서 c 와 d 는 두 톱니바퀴의 톱니 수입니다. 기어 장치는 물림들을 이어 붙인 사슬

$$c_1:d_1 ;; c_2:d_2 ;; \dots ;; c_m:d_m$$

이며, 각 물림의 두 번째 톱니바퀴가 다음 물림의 첫 번째 톱니바퀴와 같은 축을 공유합니다(즉 $1 \le i < m$ 에 대해 톱니바퀴 $d_i$ 와 톱니바퀴 $c_{i+1}$ 이 같은 축에 있습니다). 첫 번째 톱니바퀴가 한 바퀴 돌면 마지막 톱니바퀴는

$$\prod_{i=1}^{m} \frac{c_i}{d_i}$$

바퀴만큼 돌며, 이 곱이 바로 그 장치가 만들어 내는 비율입니다.

예를 들어 톱니 수가 6, 12, 30 인 톱니바퀴가 있을 때 비율 $4:5$ 는 물림 사슬 12:30 12:6 으로 만들 수 있습니다. $\frac{12}{30}\cdot\frac{12}{6}=\frac{4}{5}$ 이기 때문입니다. 반면 비율 $1:6$ 은 이 톱니바퀴들로는 만들 수 없습니다.

각 크기의 톱니바퀴는 무한히 쓸 수 있고 물림의 개수에도 제한이 없습니다. 사용할 수 있는 톱니바퀴 크기들과 목표 비율 $a:b$ 가 주어질 때, 정확히 그 비율을 만들어 내는 기어 장치가 존재하는지 판정하세요.

입력은 여러 개의 톱니바퀴 세트로 이루어지며, 각 세트 뒤에는 판정할 비율 목록이 옵니다.

각 세트는 첫 수가 $n$ ($1 \le n \le 20$) 인 한 줄로 시작합니다. $n$ 은 서로 다른 톱니바퀴 크기의 개수이며, 그 뒤에 $n$ 개의 크기 $a_1, \dots, a_n$ 이 옵니다. 모든 톱니바퀴의 톱니 수는 5 이상 100 이하이고, 각 톱니바퀴의 톱니 수는 그 세트에서 가장 작은 톱니바퀴의 톱니 수로 나누어떨어집니다. 각 크기의 톱니바퀴는 무한히 공급됩니다.

크기 목록 다음에는 비율 목록이 옵니다. 각 비율은 두 정수 $a_j$ 와 $b_j$ ($1 \le a_j, b_j \le 10000$, $a_j \ne b_j$) 로 이루어진 한 줄이며 비율 $a_j : b_j$ 를 뜻합니다. 0 0 인 줄은 현재 세트의 비율 목록이 끝났음을 나타냅니다.

마지막 세트 뒤에는 (톱니바퀴 개수 자리에) 0 하나만 있는 줄이 나와 입력의 끝을 알립니다.

각 톱니바퀴 세트마다 한 구역(section)을 출력합니다. 구역은 Set #k 줄로 시작하며, $k$ 는 1부터 시작하는 세트 번호입니다.

그다음, 입력에 주어진 순서대로 각 비율에 대해 한 줄씩 출력합니다. 그 세트의 톱니바퀴로 비율 $a_j : b_j$ 를 만들 수 있으면

Ratio aj:bj: Possible

을, 만들 수 없으면

Ratio aj:bj: Impossible

을 출력합니다. 여기서 $a_j$ 와 $b_j$ 는 입력에 주어진 값을 그대로 사용합니다.

각 구역 뒤에는 빈 줄을 하나 출력합니다.