Making Chess Boards (Small)

Chess boards are made from the bark of a very rare tree. The bark is stripped off and unrolled into one large rectangular grid of black and white cells.

Your task is to cut square chess boards out of that bark, as large as possible. A chess board is a square piece of the bark whose sides are parallel to the sides of the bark rectangle and whose cells alternate in color, so two cells that share an edge always have different colors.

Every cut takes the largest chess board that can still be formed from the bark that is left. Cells that have already been cut out are gone from the bark, so a later chess board cannot use them. If several chess boards of that largest size are available, take the topmost one, and if several of those are still tied, take the leftmost one. Repeat until no bark is left. You may need to go as far as cutting out $1 \times 1$ chess boards.

The picture below shows one sheet of bark and the first few chess boards cut out of it.

The first line contains the number of test cases $T$. The first line of each test case contains the dimensions of the bark grid, $M$ and $N$. The next $M$ lines each contain a hexadecimal integer of $N/4$ digits that represents one row of the grid. In binary that integer gives $N$ bits, one bit per cell. A 0 is a black cell and a 1 is a white cell. Rows are given from top to bottom, and inside a row the most significant bit of the hexadecimal integer is the leftmost cell.

Limits

• $1 \le T \le 100$
• $1 \le M \le 32$
• $1 \le N \le 32$, and $N$ is divisible by 4.
• Each hexadecimal integer has exactly $N/4$ digits and uses only the digits 0 to 9 and the uppercase letters A to F.

For each test case, print one line in the form "Case #x: $K$", where x is the case number starting from 1 and $K$ is the number of different chess board sizes produced by the procedure above. Then print $K$ lines, each with two integers: a chess board size and how many chess boards of that size were cut out. Print the sizes from the largest to the smallest.

The first test case of example 1 is the bark shown in the picture above.