# Which algo can be used for this problem. need solution to this.

You want to cut a piece of paper by a certain fixed rule to make some pieces of white or blue colored square paper with various sizes.
If the size of the entire paper is N×N (N = 2^K; 1 ≤ K ≤ 7; K = natural number), the cutting rules are as below.

‘If the entire piece of paper is not colored the same, cut the middle part horizontally and vertically to divide it into the same sized four pieces of paper, (N/2)×(N/2),For each divide again in the same way if one entire piece of paper is not colored the same, and make them into the same sized four pieces of paper. Continue until each and every piece of paper has only one color of white or blue.’

If the length of an edge of the first given piece of paper, N, and the color information (white or blue) inside each square are given, create a calculation program that assesses how many white/blue pieces of paper are.

Input format

Input may include many test cases. The number of test cases, T, is given on the first line of input and then the amount of T of test cases is given in a line. (T ≤ 30)
The length of an edge of the first given piece of paper, N, is given for the first line of each test case.
From the next line through to the amount of N lines, the color information is given separately as blanks. 0 indicates white and 1 indicates blue.

Input Example
2
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

Output Example

9 7

This can be solved using backtracking algorithm.