Ratings Percentage Index

In the United States, 350 schools compete every year for an invitation to the NCAA college basketball tournament. With that many schools, how do you decide who gets invited? Most teams never play each other, and some teams have a much harder schedule than others.

Here is an example schedule for four teams named A, B, C and D.

  |ABCD
 A|.11.
 B|0.00
 C|01.1
 D|.10.

Each 1 in a team's row is a win and each 0 is a loss. Team C has wins against B and D and a loss against A. Team A has wins against B and C, but has not played D.

The tournament committee uses a formula called the RPI (Ratings Percentage Index) to help rank teams. It has traditionally been defined like this.

$RPI = 0.25 \times WP + 0.50 \times OWP + 0.25 \times OOWP$

WP, OWP and OOWP are defined for each team as follows.

• WP (winning percentage) is the fraction of your games that you have won. In the example schedule, team A has WP = 1, team B has WP = 0, team C has WP = 2/3, and team D has WP = 0.5.
• OWP (opponents' winning percentage) is the average WP of all your opponents, computed after first throwing out the games they played against you. If you throw out the games played against team D, then team B has WP = 0 and team C has WP = 0.5, so team D has OWP = 0.5 × (0 + 0.5) = 0.25. In the same way team A has OWP = 0.5, team B has OWP = 0.5, and team C has OWP = 2/3.
• OOWP (opponents' opponents' winning percentage) is the average OWP of all your opponents, using exactly the OWP values computed in the previous step. Team A has OOWP = 0.5 × (0.5 + 2/3) = 7/12.

Putting it together, team A has RPI = (0.25 × 1) + (0.5 × 0.5) + (0.25 × 7/12) = 31/48.

You can ask some interesting questions about the RPI. Is it a reasonable measure of a team's ability? Does it matter more to win games or to schedule strong opponents? Your task here is more straightforward: given a schedule of games, compute the RPI of every team.

The first line of the input contains the number of test cases $T$. Each test case begins with a line containing the number of teams $N$.

The next $N$ lines each contain exactly $N$ characters. Each character is '0', '1' or '.', and together they describe a schedule in the same format as the example above. A '1' in row i, column j means team i beat team j. A '0' in row i, column j means team i lost to team j. A '.' in row i, column j means team i never played team j.

Limits

• $1 \le T \le 20$
• $3 \le N \le 10$
• If row i, column j is '1', then row j, column i is '0'.
• If row i, column j is '0', then row j, column i is '1'.
• If row i, column j is '.', then row j, column i is '.'.
• Every team plays at least two other teams.
• No two teams play each other twice.
• No team plays itself.

For each test case, print $N + 1$ lines. The first line is Case #x:, where x is the test case number starting from 1. The next $N$ lines hold the RPI of each team, one per line, in the same order as the schedule.

Every RPI is a rational number, so print it as an irreducible fraction p/q. The denominator q must be positive and the greatest common divisor of p and q must be 1. Write the denominator even when the value is an integer, so a value of 0 is printed as 0/1.