체스판 만들기 (스몰)

체스판은 아주 희귀한 나무의 껍질로 만든다. 나무에서 벗겨 낸 껍질을 넓게 펼치면 검은 칸과 흰 칸으로 이루어진 큰 직사각형 격자가 된다.

이 껍질에서 정사각형 체스판을 최대한 크게 잘라 내려고 한다. 체스판은 껍질에서 잘라 낸 정사각형 조각으로, 네 변이 껍질의 변과 평행하고, 변을 맞대고 있는 두 칸의 색이 항상 서로 다르다.

한 번 자를 때마다 지금 남아 있는 껍질에서 만들 수 있는 가장 큰 체스판을 잘라 낸다. 이미 잘라 낸 칸은 껍질에서 사라지므로 뒤에 자르는 체스판에 쓸 수 없다. 가장 큰 체스판이 여러 개면 그중 가장 위에 있는 것을 고르고, 그래도 여러 개면 그중 가장 왼쪽에 있는 것을 고른다. 껍질이 하나도 남지 않을 때까지 이 과정을 반복한다. 마지막에는 $1 \times 1$ 체스판까지 잘라 내야 할 수도 있다.

아래 그림은 껍질 한 장과 거기서 가장 먼저 잘라 내는 체스판 몇 개이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 껍질 격자의 크기 $M$과 $N$이 주어진다. 이어지는 $M$개의 줄에는 격자의 한 행을 나타내는 $N/4$자리 16진수가 한 개씩 주어진다. 이 수를 2진수로 바꾸면 $N$개의 비트가 되고, 비트 하나가 칸 하나를 나타낸다. 0은 검은 칸, 1은 흰 칸이다. 행은 위에서 아래 순서로 주어지고, 한 행 안에서는 16진수의 최상위 비트가 가장 왼쪽 칸에 해당한다.

제한

• $1 \le T \le 100$
• $1 \le M \le 32$
• $1 \le N \le 32$이고, $N$은 4의 배수이다.
• 16진수는 정확히 $N/4$자리이고, 0부터 9까지의 숫자와 A부터 F까지의 대문자만 쓴다.

각 테스트 케이스마다 "Case #x: $K$" 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, $K$는 위 과정으로 잘라 낸 체스판 크기의 종류 수이다. 이어서 $K$개의 줄에 체스판의 크기와 그 크기로 잘라 낸 체스판의 개수를 한 줄에 두 정수로 출력한다. 크기가 큰 것부터 작은 것 순으로 출력한다.

예제 1의 첫 번째 테스트 케이스가 위 그림의 껍질이다.