체스판 만들기 (라지)

체스판 산업이 어려운 시기를 맞아 도움이 필요하다. 체스판이 아주 희귀한 크로아티아 체스판 나무(Biggus Mobydiccus)의 껍질로 만들어진다는 사실은 잘 알려져 있지 않다. 이 나무의 껍질을 벗겨 펼치면 검은 칸과 흰 칸이 격자로 늘어선 커다란 직사각형 판이 된다.

당신이 할 일은 큰 정사각형 체스판을 최대한 많이 잘라내는 것이다. 여기서 체스판이란 껍질에서 잘라낸 정사각형 조각으로, 네 변이 껍질 직사각형의 변과 평행하고, 같은 색 칸 두 개가 절대 변을 맞대지 않도록 칠해져 있는 것을 말한다.

체스판을 하나 잘라낼 때마다 남아 있는 껍질에서 만들 수 있는 가장 큰 체스판을 골라야 한다. 그런 체스판이 여러 개면 가장 위쪽에 있는 것을 고르고, 그래도 여러 개면 가장 왼쪽에 있는 것을 고른다. 껍질이 하나도 남지 않을 때까지 이 과정을 반복한다. 1×1짜리 작은 체스판까지 잘라내야 하는 경우도 있다.

아래 그림은 체스판 나무의 껍질과 거기에서 가장 먼저 잘라내는 체스판 몇 개를 보여준다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 껍질 격자의 크기 $M$과 $N$이 주어진다. $N$은 항상 4의 배수이다. 다음 $M$개의 줄에는 각각 $N/4$글자짜리 16진수 정수가 주어지며, 이 정수를 2진수로 나타내면 격자 한 행에 해당하는 $N$개의 비트가 된다. 0은 검은 칸, 1은 흰 칸이다. 행은 위에서 아래 순서로 주어진다. 각 행에서 16진수 정수의 최상위 비트가 그 행의 가장 왼쪽 칸에 대응한다.

제한

• $1 \le T \le 100$
• $1 \le M \le 512$
• $1 \le N \le 512$이고 $N$은 4의 배수이다.
• 16진수 정수는 정확히 $N/4$글자이다.
• 문자는 0-9와 A-F만 쓰인다.
• 입력 파일의 크기는 200kB 이하이다.

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

첫 번째 예제 입력이 위 그림의 껍질에 해당한다.