Construct Quad Tree

You are given a square matrix ‘matrix of size ‘N’ containing 0’s and 1’s only. You have to represent the matrix as a Quad-Tree.

A Quad-Tree is a tree data structure where each node has exactly four children 'topLeft', 'topRight', 'bottomLeft', 'bottomRight', 'bottomLeft'. All nodes have two attributes, 'value': 1 if the node represents a grid of 1's or 0 if the node represents a grid of 0's and 'isLeaf': true if the node is leaf node on the tree or false if the node has the four children.

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e., all 1's or all 0's) set isLeaf to true and set 'value' to the value of the grid and set the four children to null and stop.

If the current grid has different values, set “isLeaf” to false and set value to  -1, and divide the current grid into four sub-grids as shown in the image.

Repeat the above steps for each of the children with the proper sub-grid.

Input Format

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The 1st line of each test case contains one integer 'N', representing the size of the square matrix.

The next 'N' lines contain 'N' integers separated by spaces describing rows of matrix 'matrix' (each element of ‘matrix’ is either 0 or 1).

Output Format

The output represents the Quad-Tree in a level order manner, with each node represented as a comma-separated value isLeaf, value.

If the value of “isLeaf” or “value” is 1 we represent it as 1, 1, and if the value of “isLeaf” or “value” is 0 we represent it as 0, 0, and if the “value” is -1 we represent it as -1.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
N = 2^y where 0 <= y <= 10
matrix[i][j] = 0 or 1

Time Limit: 1 second