Problem: boomerang_tournament (2016 round1)

This weekend, the long-awaited BIT (Boomerang Invitational Tournament) will be
taking place! **N** of the finest boomerangists will be competing in a
randomly-seeded single-elimination bracket.

For those unfamiliar with this tournament format, the process can be modelled
as follows:

  1. The **N** competitors are arranged in a queue (an ordered list), in some order 
  2. If the queue currently contains only 1 competitor, the tournament ends with them as the champion 
  3. Otherwise, the first 2 competitors in the front of the queue are removed, and they play a match against one another 
  4. The winner of that match is re-inserted into the queue, at the back 
  5. Repeat from step 2 

The one-on-one matches in this tournament are, of course, boomerang duels to
the death. If the **i**th and **j**th competitors face off against one
another, the **i**th competitor will win if **Wi,j** = 1. Otherwise, if
**Wi,j** = 0, the **j**th competitor will win. Note that, for all (1 ≤ **i**,
**j** ≤ **N**), **Wi,j** = 0 or 1, and **Wi,i** = 0 (no one will play against
themselves anyway), and **Wi,j** ≠ **Wj,i** (if **i** ≠ **j**). Those are the
only constraints. It's possible that, for example, competitor A can beat B, B
can beat C, and C can beat A.

Once the tournament is over, each boomerangist is given a placing (even if
they didn't survive the competition). A given competitor **c**'s placing is an
integer one greater than the number of competitors who won strictly more
matches than **c** did.

For each boomerangist, you'd like to know both the best (smallest) and the
worst (largest) placing they could possibly end up with, given that the
initial ordering of the competitors (in step 1 of the tournament) is unknown.

### Input

Input begins with an integer **T**, the number of tournaments. For each
tournament, there is first a line containing the integer **N**. Then follow
**N** lines, the **i**th of which contains the space-separated integers
**Wi,1** through **Wi,N**.

### Output

For the **i**th tournament, print a line containing "Case #**i**: " followed
by **N** lines that each contain two space-separated integers. The first
integer on the **i**th line should be the best possible placing for the
**i**th competitor, and the second should be the worst possible placing.

### Constraints

1 ≤ **T** ≤ 250  
**N** = 2**K** where **K** is an integer and 0 ≤ **K** ≤ 4   

### Explanation of Sample

In the second tournament, the first competitor will always beat the second
competitor, so the first competitor will finish in 1st place, and the other in
2nd place. In the third tournament, the first competitor never loses, so they
will finish in 1st place. The fourth competitor never wins, so they will
finish tied for 3rd place with the other competitor who loses their initial
match. The other two competitors will either lose their first match (if
initially paired with the first competitor) or their second match (if
initially paired with the fourth competitor), so they can each finish in 2nd
place, or tied for 3rd place.



Sample input:
5
1
0
2
0 1
0 0
4
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
4
0 0 0 0
1 0 0 1
1 1 0 0
1 0 1 0
8
0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 1 1 0 0 1 1 0
1 1 1 1 0 1 0 1
1 1 1 0 0 0 0 1
1 1 1 0 1 1 0 1
1 1 1 1 0 0 0 0


Sample output:
Case #1:
1 1
Case #2:
1 1
2 2
Case #3:
1 1
2 3
2 3
3 3
Case #4:
3 3
1 3
1 3
1 3
Case #5:
5 5
3 5
3 5
1 5
1 5
2 5
1 5
1 5