G: Reading a Quadtree 

A quadtree, first introduced by Finkel and Bentley, is a tree data-structure in which each internal node has exactly four children. Quadtrees are often used for problems that can be mapped into a two-dimensional space which is then recursively subdivided it into four equally-sized regions while a certain condition holds. The problem consists in reading a compressed binary image represented with a quadtree and determining which pixels are set to white.

For a better understanding of this problem, consider the third test case from Sample Input, represented in the figure. The uncompressed binary image is composed by (8 x 8) pixels, where 35 of them are white. Notice each node in the quadtree is mapped into a square area from the target image. White nodes denote areas composed by white pixels exclusively, whereas black nodes denote areas with only black pixels; finally, gray nodes are composed by white and black pixels and thus, they need to be subdivided into four new square areas. Notice that the order of visiting square areas is: left to right and top to bottom.

\epsfbox{p11948.eps}

Input 

The first line contains an integer N > 0 denoting the number of test cases.

The next N lines start each with the length L of the target image; L has to be a power of 2.

The length is followed by a space and a sequence of 0, 1 and *, denoting black, white and gray nodes of the quadtree, respectively. The quadtree is traversed in pre-order.

Output 

The output consists of N lines containing each a comma-separated list of either:

a)
(x, y) position of a pixel adjacent horizontally by black pixels, or
b)
(xi - xf, y), where xf > xi: a sequence of white pixels at row y surrounded by black pixels.

The following holds: 1$ \le$x, xi, xf, y$ \le$L. Traverse the binary image from left to right, top to bottom.

If L is not a power of 2, the output should display the text ``Invalid length", instead.

Sample Input  

3 
4 **1000*010010 
7 *101*0100 
8 *10*011*0010*1*101010

Sample Output  

(1,1),(4,1),(1-2,3),(1-2,4) 
Invalid length 
(1-4,1),(1-4,2),(1-4,3),(1-4,4),(3-7,5),(3-7,6),(1-2,7),(5-6,7),(1-3,8),(5-6,8)