RPI (Large)

In the United States, 350 schools compete every year for an invitation to the NCAA college basketball tournament. With that many schools, deciding who should be invited is hard. 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, 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, and has not played D.

The tournament committee uses a formula called the RPI (Ratings Percentage Index) to help rank teams. It is 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, taken 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 \times (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 \times (0.5 + 2/3) = 7/12$.

Putting it together, team A has $RPI = (0.25 \times 1) + (0.5 \times 0.5) + (0.25 \times 7/12) = 0.6458333\ldots$

You can ask whether the RPI measures a team's ability well, or whether winning games matters more than scheduling strong opponents. This problem asks for something simpler. Given a schedule of games, calculate every team's RPI.

The first line 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 of them '0', '1' or '.', giving a schedule in the format shown 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, and a '.' in row i, column j means team i never played team j.

Limits

• $1 \le T \le 20$
• 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.
• $3 \le N \le 100$

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 contain the RPI of each team, one per line, in the order the schedule lists them. Round each RPI to the ninth digit after the decimal point and print exactly nine digits.