题目描述

二进制图像（如图2(a)所示）通常用二进制数组表示，数组中的每个元素为0或1（如图2(b)）。为存储这类图像，常使用四叉树分割法：

• 对于一个N×N的数组（N≤512且为2的幂），若所有元素值相同，则无需分割；
• 否则，将其分割为4个N/2×N/2的子数组（如图2(c)），对每个子数组递归应用上述规则，直到所有子数组内的元素值唯一。
  

四叉树的存储方式如下：

• 根节点代表原始数组。
• 若节点对应数组需分割（即元素值不唯一），则节点值为1，且包含四个子节点。
• 若节点对应数组无需分割，节点值为0，后跟该数组的元素值（0或1）。

将四叉树的节点值按层序遍历（从根到叶子，每层从左到右）排列，删除括号和逗号后得到一个二进制串。本题要求将该二进制串转换为十六进制输出。

输入格式

• 第一行包含整数k（1≤k≤100），表示测试用例数。
• 每个测试用例：
  • 第一行是整数N（N≤512且为2的幂），表示图像大小为N×N。
  • 后续N行，每行包含N个用空格分隔的二进制数（0或1），表示图像数组。

输出格式

对每个测试用例，输出对应的二进制串的十六进制表示。

输入示例 1

3  
2  
0 0  
0 0  
4  
0 0 1 1  
0 0 1 1  
1 1 0 0  
1 1 0 0  
8  
0 0 0 0 0 0 1 1  
0 0 0 0 0 0 1 1  
0 0 0 0 0 1 0 0  
0 0 0 0 0 1 0 0  
1 1 1 1 0 0 0 0  
1 1 1 1 0 0 0 0  
1 1 1 1 1 1 1 1  
1 1 1 1 1 1 1 1  

输出示例 1

0  
114  
258C0511  

来源

亚洲高雄竞赛 2003