Quad Trees

A binary image like the one in Figure 2(a) is normally stored as an array whose entries are 0 or 1. Figure 2(b) is the array for the image in Figure 2(a). To store such an image in less space, use the quad tree partition.

Take an $N \times N$ array with $N \le 512$ and $N = 2^i$ for some positive integer $i$. If its entries are not all equal, split it into four $N/2 \times N/2$ arrays, as in Figure 2(c). If one of those $N/2 \times N/2$ arrays still holds both values, like the upper right and the lower right ones in Figure 2(c), split it into four $N/4 \times N/4$ arrays. Those arrays can be split again into four $N/8 \times N/8$ arrays, and so on. The partition stops once every piece holds a single value. Figure 2(c) is the finished partition.

Figure 2: a binary image (a), its array representation (b), its quad tree partition (c), and its quad tree representation (d).

Instead of the image itself, store the quad tree of Figure 2(d), which encodes Figure 2(c). Each node of the tree stands for one array of Figure 2(c), and the root stands for the whole array. A node whose value is 1 means that its array is split into four smaller arrays. Otherwise the node carries two values and the first one is 0, which means that its array is not split any further. In that case the second value is 0 if every entry of the array is 0, and 1 if every entry is 1. The four children of a split node are listed in the order upper left, upper right, lower left, lower right.

The tree of Figure 2(d) is written as (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). This lists the node values from the root down to the leaves, left to right inside each level. Delete the parentheses and the commas and the result is the binary number 100101100011000000010100010001, which is 258C0511 in hexadecimal. Write a program that computes this hexadecimal value for each given image.

The first line has an integer $k$ with $1 \le k \le 100$, the number of test cases. Each test case begins with a line holding a positive integer $N$, the side length of the binary image, where $N \le 512$ and $N = 2^i$ for some positive integer $i$. The $N \times N$ binary array follows, with at least one blank between two elements.

For each test case, print on its own line the bit stream that codes the input array, written in hexadecimal. Use uppercase letters for the digits A to F, and print no leading zeros, so a code whose value is zero prints as a single 0.