棋盘工业正处于困境，需要你的帮助。鲜为人知的是，棋盘是由极其罕见的克罗地亚棋盘树（Biggus Mobydiccus）的树皮制成的。树皮被剥下并展开成一张巨大的矩形棋盘材料。这个矩形是一个由黑白方格组成的网格。

你的任务是尽可能多地制作大型方形棋盘。棋盘是一块树皮，它是一个正方形，其边与树皮矩形的边平行，且单元格按照棋盘图案着色（没有两个相同颜色的单元格共享一条边）。

每次切割棋盘时，你必须选择剩余材料中可能的最大棋盘。如果存在多个这样的棋盘，选择最靠上的一个。如果仍然有平局，则选择最靠左的一个。继续切割棋盘，直到没有剩余的树皮为止。你可能需要一直切割到 $1 \times 1$ 的迷你棋盘。

下图展示了一块棋盘树的树皮以及从中切割出的前几个棋盘。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含树皮网格的尺寸 $M$ 和 $N$。$N$ 总是 4 的倍数。接下来的 $M$ 行，每行包含一个长度为 $N/4$ 的十六进制整数，代表树皮网格的一行。这些整数的二进制表示给出了 $N$ 位的字符串，对应每一行。零代表黑色方格；一代表白色方格。输入中的行是从上到下给出的。在每一行中，十六进制整数的最高有效位对应于该行最左侧的单元格。

输出格式

对于每个测试用例，输出一行，包含 "Case #x: $K$"，其中 $x$ 是用例编号（从 1 开始），$K$ 是按照上述过程切割出的不同棋盘尺寸的数量。接下来的 $K$ 行，每行包含两个整数——棋盘的尺寸（从大到小排列）以及该尺寸棋盘的数量。

数据范围

$1 \le T \le 100$； $N$ 是 4 的倍数； 每个十六进制整数恰好包含 $N/4$ 个字符； 仅使用字符 0-9 和 A-F。

小数据集（测试集 1 - 可见；18 分）

$1 \le M \le 32$； $1 \le N \le 32$。

大数据集（测试集 2 - 隐藏；24 分）

$1 \le M \le 512$； $1 \le N \le 512$； 输入文件大小不超过 200kB。

样例

样例输入 1

4
15 20
55555
FFAAA
2AAD5
D552A
2AAD5
D542A
4AD4D
B52B2
52AAD
AD552
AA52D
AAAAA
5AA55
A55AA
5AA55
4 4
0
0
0
0
4 4
3
3
C
C
4 4
6
9
9
6

样例输出 1

Case #1: 5
6 2
4 3
3 7
2 15
1 57
Case #2: 1
1 16
Case #3: 2
2 1
1 12
Case #4: 1
2 4

说明

第一个样例测试用例代表了上图所示的情况。