The town of Pezinok wants to expand by building a new neighborhood. They hired some famous architects to design it, and your friend Jano is one of them. He is in charge of the road network. It is common to make one-way roads these days, so Jano went all out and decided to make all the roads one-way. (Of course, a pair of junctions can be connected by two roads – one in each direction.)
Once Jano made a map showing the planned roads, he noticed that some parts of the neighborhood might not be reachable from other parts. To estimate the impact of this issue, he decided to use a systematic approach: he took a piece of paper and wrote everything down. Namely, for each junction j he listed all other junctions that are (directly or indirectly) reachable from j. We call this information the reachability list of a road network.
But then Jano’s hard drive crashed and he lost all the plans he had made. The only thing he has left is the piece of paper with the reachability list.
Help Jano reconstruct his original road network. Of course, many different road networks can produce the same reachability list. Therefore, Jano asked you to find the smallest possible road network that has the given reachability list. That should help him reconstruct his original plans.
Find a road network with the smallest possible number of roads that has the given reachability list.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case starts with a line containing an integer n, denoting the number of junctions. The junctions are numbered 1 through n. Next, n lines follow, each containing a string of length n. The i-th of these lines specifies which junctions are reachable from junction i. Namely, the j-th character in the line is 1 if junction j is reachable from i and 0 otherwise. (Note that for each i, junction i is reachable from itself.)
The reachability list is consistent – it describes at least one real road network.
In the easy subproblem U1 you may further assume that the reachability list is special: for every pair of junctions a ≠ b, either a is reachable from b or b is reachable from a, but never both.
For each test case, output the smallest road network that corresponds to the given reachability list. The first line of the description should contain the number of roads m (which has to be as small as possible). Each of the next m lines should contain two integers ai and bi (1 ≤ ai, bi ≤ n) such that there is a one-way road going from junction ai to junction bi.
You can print the roads in any order. If there are multiple optimal solutions, output any of them.
Input:
2
3
111
011
001
4
1111
1111
0011
0011Output:
2
1 2
2 3
5
1 2
2 1
1 3
3 4
4 3The first test case satisfies the additional constraint for the easy subproblem.
In the second test case, we know that all junctions should be interconnected, except that junctions 1 and 2 should not be reachable from junctions 3 and 4. The smallest road network with this property has five one-way roads. One such road network is shown in the example output above. This test case also has other optimal solutions.