Messed Up Pictures

Someone messed up the pictures on your friend's computer. Most of the image files were cropped, rotated by 90 degrees, or both, and the rest were left alone. Your friend still remembers the list of aspect ratios of all the original images.

The aspect ratio of an image of size $(A, B)$ is $(A / G, B / G)$, where $G$ is the greatest common divisor of $A$ and $B$.

The contents of an image do not matter here, so a rotation swaps the width and the height. A crop selects a rectangle with integer side lengths inside the image, with its sides parallel to the sides of the image, and the selected rectangle is smaller than the image it is taken from.

Every messed up image was produced from its original by applying at most one crop and at most one rotation, in either order.

You are given the size of every messed up image and the list of possible aspect ratios. For each image, print one possible original size and the number of operations used to mess it up.

The first line contains one integer $T$ ($1 \le T \le 100$), the number of test cases.

Each test case starts with a line containing one integer $M$ ($1 \le M \le 100$), the number of possible aspect ratios. Each of the next $M$ lines contains two integers $R_x$ and $R_y$ ($1 \le R_x \le R_y \le 100$) describing one aspect ratio. The greatest common divisor of $R_x$ and $R_y$ is always 1, and all aspect ratios inside one test case are distinct.

The next line contains one integer $N$ ($1 \le N \le 100$), the number of messed up images. Each of the next $N$ lines contains two integers $X$ and $Y$ ($1 \le X, Y \le 100$), the size of one messed up image.

For each test case, print a line Case n:, where $n$ is the number of the test case counting from 1. Then print $N$ lines, one per image, each containing three integers $W$, $H$ and $K$ separated by single spaces.

$W$ and $H$ are a possible original size of that image. With $G$ the greatest common divisor of $W$ and $H$, the pair $(W / G, H / G)$ must equal one of the given aspect ratios. $K$ is the number of operations used to mess the image up, so $K$ is 0 when nothing changed, 1 when the image was only cropped or only rotated, and 2 when it was both cropped and rotated.

If several answers are possible, print the one with the smallest $W \times H$. If several remain, print the one with the smallest $W$. If several still remain, print the one with the smallest $K$.