Binary Puzzle
-------------

The Toronto Comet plans to introduce a new type of puzzle,
a binary puzzle.  Such a binary puzzle consists of an n x n grid, 
where n is even.  Some of the cells of the grid contain zeroes, 
some contain ones, and the remaining cells are empty.  Readers 
should fill the empty cells with zeroes and ones such that
- in each row and each column there are at most two consecutive 
  zeroes,
- in each row and each column there are at most two consecutive 
  ones,
- each row contains the same number of zeroes as ones, and
- each column contains the same number of zeroes as ones.
To ensure that the binary puzzles to be published in the Toronto
Comet are solvable, we need your help.  You are asked to write
a program that takes binary puzzles as input and checks if they
can be solved.

Input
-----
Input consists of several lines.  The first line contains an 
positive integer p, which is the number of puzzles.  Each puzzle 
is described by several lines of input.  The first line of each
puzzle description contains an integer n, which is positive and 
even (n <= 8).  This line is followed by n lines, each consisting
of n characters (either '0', '1' or ' ').

Output
------
The output consists of one line for each puzzle.  That line 
consists of true if the puzzle can be solved and false otherwise.

Sample input
------------
2
4
00 0
  0 
  0 
1010
8
         
         
         
         
         
         
         
         

Sample output
-------------
false
true