망가진 사진

누군가가 친구의 컴퓨터에 있던 사진을 망가뜨렸다. 이미지 파일 대부분은 잘리거나, 90도 회전했거나, 둘 다 당했고 나머지는 그대로 남았다. 다행히 친구는 원본 이미지 전체의 화면비 목록을 아직 기억한다.

크기가 $(A, B)$인 이미지의 화면비는 $(A / G, B / G)$이고, $G$는 $A$와 $B$의 최대공약수다.

이미지의 내용은 상관없으므로 회전은 가로와 세로를 맞바꾸는 연산이다. 자르기는 이미지 안에서 각 변이 이미지의 변과 평행하고 변의 길이가 정수인 직사각형을 고르는 연산이며, 고른 직사각형은 잘라내기 전의 이미지보다 작다.

망가진 이미지는 모두 원본에 자르기를 최대 한 번, 회전을 최대 한 번 적용해서 만들어졌고, 두 연산의 순서는 상관없다.

망가진 이미지의 크기와 가능한 화면비 목록이 주어진다. 이미지마다 원본 크기로 가능한 값 하나와 망가뜨리는 데 쓴 연산의 수를 출력하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 가능한 화면비의 수 $M$ ($1 \le M \le 100$)이 주어진다. 이어지는 $M$개의 줄에는 화면비 하나를 나타내는 두 정수 $R_x$와 $R_y$ ($1 \le R_x \le R_y \le 100$)가 주어진다. $R_x$와 $R_y$의 최대공약수는 항상 1이고, 한 테스트 케이스 안의 화면비는 모두 서로 다르다.

다음 줄에는 망가진 이미지의 수 $N$ ($1 \le N \le 100$)이 주어진다. 이어지는 $N$개의 줄에는 망가진 이미지 하나의 크기를 나타내는 두 정수 $X$와 $Y$ ($1 \le X, Y \le 100$)가 주어진다.

각 테스트 케이스마다 먼저 Case n: 형식의 줄을 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호다. 그 다음 이미지마다 한 줄씩 총 $N$개의 줄에 공백 하나로 구분한 세 정수 $W$, $H$, $K$를 출력한다.

$W$와 $H$는 그 이미지의 원본 크기로 가능한 값이다. $W$와 $H$의 최대공약수를 $G$라 할 때 $(W / G, H / G)$는 주어진 화면비 중 하나와 같아야 한다. $K$는 망가뜨리는 데 쓴 연산의 수로, 아무것도 바뀌지 않았으면 0, 자르기만 했거나 회전만 했으면 1, 자르기와 회전을 모두 했으면 2다.

답이 여러 개면 $W \times H$가 가장 작은 것을 출력한다. 그래도 여러 개면 $W$가 가장 작은 것을, 그래도 여러 개면 $K$가 가장 작은 것을 출력한다.