你的朋友电脑里有很多很棒的图片，直到有人把它们弄乱了。她发现她的大多数图片文件要么被裁剪过，要么被旋转了 90 度，或者根本没有改变。幸运的是，她还记得她所有图片原始的宽高比集合。

对于尺寸为 $(A, B)$ 的图像，其宽高比定义为 $(A / G, B / G)$，其中 $G$ 是 $A$ 和 $B$ 的最大公约数（GCD）。

由于我们不关心图像内容，旋转操作即交换宽度和高度。裁剪操作是指在原始图像内选择一个较小的矩形（具有整数尺寸），且其边应与原始图像的边平行。

你的任务是帮助她确定每张图片可能的原始尺寸。给定被弄乱的图像尺寸以及可能的宽高比，输出每张图片可能的原始尺寸以及为了弄乱它所进行的操作次数。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例以一行包含整数 $M$ ($1 \le M \le 100$) 开始，表示可能的宽高比数量，随后是 $M$ 行，每行包含 2 个整数 $Rx$ 和 $Ry$ ($1 \le Rx \le Ry \le 100$)，表示第 $i$ 个宽高比（对于任何给定的宽高比，$Rx$ 和 $Ry$ 的 GCD 始终为 1），同一测试用例中的所有宽高比各不相同。下一行包含一个整数 $N$ ($1 \le N \le 100$)，表示被弄乱的图像数量，随后是 $N$ 行，每行包含 2 个整数 $X$ 和 $Y$ ($1 \le X, Y \le 100$)，表示第 $i$ 张被弄乱图像的尺寸。

输出格式

对于每个测试用例，打印一行包含 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 1 开始），随后是 $N$ 行，每行应包含 3 个由空格分隔的整数 $W$、$H$ 和 $K$，$W$ 和 $H$ 表示第 $i$ 张被弄乱图像可能的原始尺寸（$W$ 和 $H$ 的比值应为给定的宽高比之一），$K$ 表示弄乱它所使用的操作次数（如果未进行任何更改，则 $K$ 应为 0；如果进行了裁剪或旋转，则为 1；如果既进行了裁剪又进行了旋转，则为 2）。

对于每张图像，如果存在多个解，请打印使 $W \times H$ 最小的解。如果仍有多个解，请打印使 $W$ 最小的解。如果仍有多个解，请打印使 $K$ 最小的解。

样例

样例输入 1

1
1
3 4
5
3 4
4 3
2 4
4 2
5 6

样例输出 1

Case 1:
3 4 0
3 4 1
3 4 1
3 4 2
6 8 1