U275119 SNTT战队的像素画图章（normal version2）

#### *Tips ：这是本题的求最少所需操作次数的版本。 ------------ Sanitater战队最近想要给自己的队伍画一个像素画图章。他们希望拥有一个由n * n大小的像素画点阵图作为他们战队的灵魂象征。 他们的队员商讨了许久，最终选择了队内的CangShuV去作画。画作的内容可以被描述为一个n * n大小的矩阵。这幅画将只由两种颜色构成。每种颜色可能出现多次。其中，第一种颜色将用0表示，第二种颜色将用1表示。 然而，由于EA的土豆服务器承载不起无限的图章图层，这幅画将只能被k个图层描绘。换而言之，你只能使用k个可随意伸缩旋转的实心矩形去绘制这幅像素画。每个矩形只能被染成一种颜色。矩形之间可以以任何方式互相覆盖遮挡。你可以假设图章绘制最初时的每个像素点都是透明像素（颜色值为-1）。 因此，他们想知道最少需要多少个图层才能绘制出这幅像素画。即求矩形的最少数量。 鉴于他们队伍里的每个人都忙着捞薯条，于是他们找到了你去解决这个问题。 你能帮助他们找到这个问题的解决方案吗？

数据的第一行会给出一个整数t代表数据组数， 而后每一组数据的第一行将会给出n的数值。 接下来，每一组数据的第二行开始，将以上述规则逐行描述像素画的内容。 输入保证不会出现没有颜色的像素。

每行输出一个整数，代表每组数据所用矩形的最少数量。

在第一组数据中，可以先画一个3 * 3大小的颜色为1的矩形，而后用两个1 * 2大小的颜色为0的矩形覆盖部分原来的矩形。可以证明，最少也需要3个图层才能画出这幅画。 ```c Step1. 1 1 1 1 1 1 1 1 1 Step2. 0 0 1 1 1 1 1 1 1 Step3. 0 0 1 0 1 1 1 1 1 ``` 在第二组数据中，只需要一步即可画出这幅画。 #### 数据范围 （1