쿼드 트리

그림 2(a) 같은 이진 이미지는 보통 각 원소가 0 또는 1인 배열로 저장한다. 그림 2(b)가 그림 2(a)의 이미지를 나타내는 배열이다. 이런 이미지를 더 적은 공간에 저장할 때는 쿼드 트리 분할을 쓴다.

$N \times N$ 배열을 생각하자. $N \le 512$이고, 어떤 양의 정수 $i$에 대해 $N = 2^i$이다. 배열의 원소가 모두 같지 않으면 그림 2(c)처럼 $N/2 \times N/2$ 배열 네 개로 나눈다. 나눈 $N/2 \times N/2$ 배열에 0과 1이 섞여 있으면, 그림 2(c)의 오른쪽 위와 오른쪽 아래 배열처럼 다시 $N/4 \times N/4$ 배열 네 개로 나눈다. 이렇게 나온 배열도 필요하면 $N/8 \times N/8$ 배열 네 개로 나누고, 같은 방식을 계속한다. 조각마다 값이 한 가지만 남으면 분할이 끝난다. 그림 2(c)가 분할을 마친 모습이다.

그림 2: 이진 이미지 (a), 배열 표현 (b), 쿼드 트리 분할 (c), 쿼드 트리 표현 (d).

이미지를 그대로 저장하는 대신, 그림 2(c)를 부호화한 그림 2(d)의 쿼드 트리를 저장한다. 트리의 노드 하나는 그림 2(c)의 배열 하나를 나타내고, 루트는 배열 전체를 나타낸다. 노드의 값이 1이면 그 배열을 더 작은 배열 네 개로 나눈다는 뜻이다. 그렇지 않으면 노드에 값이 두 개 있고 첫 번째 값은 0인데, 그 배열을 더 나누지 않는다는 뜻이다. 이때 두 번째 값이 0이면 배열의 원소가 모두 0이고, 1이면 모두 1이다. 나누는 노드의 자식 네 개는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 놓는다.

그림 2(d)의 트리는 (1)(0,0)(1)(0,1)(1)(0,0)(0,1)(1)(0,0)(0,0)(0,0)(0,1)(0,1)(0,0)(0,1)(0,0)(0,1)로 적는다. 루트에서 잎까지 내려가면서 같은 레벨 안에서는 왼쪽부터 오른쪽으로 노드 값을 나열한 것이다. 괄호와 쉼표를 지우면 이진수 100101100011000000010100010001이 되고, 이 값은 16진수로 258C0511이다. 이미지마다 이 16진수 값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $k$가 주어진다. $1 \le k \le 100$이다. 각 테스트 케이스의 첫째 줄에는 이진 이미지의 한 변 길이 $N$이 주어진다. $N \le 512$이고, 어떤 양의 정수 $i$에 대해 $N = 2^i$이다. 이어서 $N \times N$ 이진 배열이 주어진다. 두 원소 사이에는 공백이 하나 이상 있다.

테스트 케이스마다 입력 배열을 부호화한 비트 스트림을 16진수로 한 줄에 출력한다. A부터 F까지는 대문자로 쓰고, 앞에 0을 붙이지 않는다. 값이 0이면 0 하나만 출력한다.