Making Chess Boards (Large)

The chess board industry has fallen on hard times and needs your help. Few people know that chess boards are made from the bark of an extremely rare tree, the Croatian Chess Board tree (Biggus Mobydiccus). The bark of that tree is stripped and unwrapped into one huge rectangular sheet of chess board material. The rectangle is a grid of black and white squares.

Your task is to cut out as many large square chess boards 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 are colored in a chess board pattern, so that no two cells of the same color share an edge.

Each time you cut out a chess board, you must choose the largest chess board left in the sheet. If several boards have that size, take the topmost one. If there is still a tie, take the leftmost one. Keep cutting out chess boards until no bark is left. You may have to go all the way down to 1 by 1 mini chess boards.

The picture below shows the bark of a Chess Board tree and the first few chess boards that are cut out of it.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each one starts with a line containing the dimensions of the bark grid, $M$ and $N$. $N$ is always a multiple of 4. The next $M$ lines each contain a hexadecimal integer of $N/4$ characters, representing one row of the bark grid. The binary form of that integer gives $N$ bits, one for each cell of the row. A zero is a black square and a one is a white square. The rows are given from top to bottom. In each row, the most significant bit of the hexadecimal integer corresponds to the leftmost cell of that row.

Limits

• $1 \le T \le 100$
• $1 \le M \le 512$
• $1 \le N \le 512$ and $N$ is divisible by 4
• Each hexadecimal integer contains exactly $N/4$ characters.
• Only the characters 0-9 and A-F are used.
• The input file is at most 200kB in size.

For each test case, output one line containing "Case #x: $K$", where x is the test case number starting from 1 and $K$ is the number of different chess board sizes that the procedure above cuts out. The next $K$ lines each contain two integers, the size of the chess board (from largest to smallest) and the number of chess boards of that size.

The first sample test case is the bark shown in the picture.