Background

Special for beginners, ^_^

Description

#地图瓦片与四叉树（一）

在瓦片地图的前世今生中介绍了地图瓦片的定义、来历，实际上我们在浏览互联网地图的时候，屏幕上的地图都是由一些小图片拼接而来，这些小图片就是地图瓦片。

在上一篇文章中数说地图投影之墨卡托地图介绍了墨卡托投影，并且提到了互联网地图也是使用了墨卡托投影，并且把地图搞成了一个正方形，长宽是等值的，这正是为了瓦片分级切割方案服务的，而这个切割方案是基于四叉树索引的。

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间，一个正方形切割成四等分，得到的依然是正方形，这就是为什么网络墨卡托投影要把地图搞成正方形的原因。

四叉树 (Quad Tree) 算法可以将大量坐标数据压缩保存，通常将给定空间分割为4个，然后以递归形式表示（此即四叉树的得名由来）。最著名的应用是对黑白图像的压缩（一个24位真彩色的图像可以看成24个黑白图像的叠加）。四叉树以字符串的形式对$2^N × 2^N$的黑白图像进行如下压缩：

若区域的图像的所有像素为黑色，则四叉树压缩的结果都是字符0（无论图像区域的大小是多少，哪怕是整幅图像）； 若区域的图像的所有像素为白色，则四叉树压缩的结果都是字符1（无论图像区域的大小是多少，哪怕是整幅图像）； 若区域图像的像素不同色，则先把图像区域纵向及横向各一分为二，然后对4个小图像区域进行四叉树压缩。而该区域图像的压缩结果字符串为*（左上部分的压缩结果）（右上部分的压缩结果）（左下部分的压缩结果）（右下部分的压缩结果）。

Format

Input

第一行给出一个正整数N，表示测试例的数量。

接下来N行给出这N个测试例。

每个测试例首先给出一个n(<=4096)，表示图像的大小。接下来是成对出现的白色矩形区域的左上角和右下角的坐标。格式为先横坐标再纵坐标，如果不是成对出现，则忽略掉最后那个落单的坐标。

Output

对每个输入的测视例，输出一行结果，总计N行。

如果图像的大小不满足大于1且是2的幂次，则输出"Size is invalid"。

否则输出四叉树，按照先序遍历的顺序输出，对于纯黑、纯白和灰色区域，分别输出0、1和*。四叉树的灰色根无需输出。

Samples

3
4 (1,1) (1,1) (4,1) (4,1) (1,3) (2,4)
15
8 (1,1) (4,4) (3,5) (7,6) (1,7) (2,8) (3,8) (3,8) (5,7) (6,8)

*1000*010010
Size is invalid
10*011*0010*1*101010

Limitation

1s, 1024KiB for each test case.