체스판 만들기

체스판 산업은 어려운 시기를 맞았으며 여러분의 도움이 필요하다. 체스판이 극도로 희귀한 Croatian Chess Board 나무의 껍질로 만들어진다는 사실은 잘 알려져 있지 않다(Biggus Mobydiccus). 이 나무의 껍질을 벗겨 펼치면 거대한 직사각형 체스판 재료 한 장이 된다. 이 직사각형은 검은색과 흰색 칸으로 이루어진 격자이다.

여러분의 임무는 가능한 한 크기가 큰 정사각형 체스판을 최대한 많이 만드는 것이다. 체스판은 나무껍질에서 잘라낸 정사각형 조각으로, 그 변은 나무껍질 직사각형의 변과 평행하고 칸은 체스판 무늬로 칠해져 있다(같은 색의 두 칸은 변을 공유할 수 없다).

체스판을 잘라낼 때마다 시트에 남아 있는 체스판 중 가능한 가장 큰 것을 선택해야 한다. 그러한 체스판이 여러 개라면 가장 위에 있는 것을 고른다. 그래도 동률이면 가장 왼쪽에 있는 것을 고른다. 나무껍질이 하나도 남지 않을 때까지 체스판을 계속 잘라낸다. 크기가 1×1인 초소형 체스판까지 잘라내야 할 수도 있다.

다음은 Chess Board 나무의 껍질과 여기서 처음 몇 개의 체스판을 잘라내는 모습을 보여 주는 예제이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100; N은 4로 나누어떨어진다; 각 십육진수 정수는 정확히 N/4개의 문자로 이루어진다. 0-9과 A-F 문자만 사용된다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ M ≤ 32; 1 ≤ N ≤ 32.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ M ≤ 512; 1 ≤ N ≤ 512; 입력 파일의 크기는 최대 200kB이다.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 나무껍질 격자의 크기 M과 N이 들어 있는 줄로 시작한다. N은 항상 4의 배수이다. 이어지는 M개의 각 줄에는 나무껍질 격자의 한 행을 나타내는 (N/4)문자 길이의 십육진수 정수가 주어진다. 이 정수들을 이진수로 표현하면 각 행마다 N개의 비트로 이루어진 문자열이 된다. 영은 격자의 검은색 칸을 나타내고, 일은 흰색 칸을 나타낸다. 입력에서 행은 위에서 아래 순서로 주어진다. 각 행에서 십육진수 정수의 최상위 비트는 그 행의 가장 왼쪽 칸에 대응한다.

각 테스트 케이스마다 "Case #x: K"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, K는 위에서 설명한 절차에 따라 잘라낼 수 있는 서로 다른 체스판 크기의 수이다. 이어지는 K개의 줄에는 각각 두 정수, 즉 체스판의 크기(큰 것부터 작은 것 순서)와 잘라낼 수 있는 해당 크기의 체스판 수를 출력한다.

첫 번째 예제 테스트 케이스는 위의 이미지를 나타낸다.