In the United States, 350 schools compete every year for an invitation to the NCAA College Basketball Tournament. With so many schools, how do you decide who should be invited? Most teams never play each other, and some teams have a much more difficult schedule than others.
Here is an example schedule for 4 teams named A, B, C, D:
|ABCD -+---- A|.11. B|0.00 C|01.1 D|.10.Each 1 in a team's row represents a win, and each 0 represents a loss. So 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 NCAA tournament committee uses a formula called the RPI (Ratings Percentage Index) to help rank teams. Traditionally, it has been defined as follows:
RPI = 0.25 * WP + 0.50 * OWP + 0.25 * OOWPWP, OWP, and OOWP are defined for each team as follows:
There are some pretty interesting questions you can ask about the RPI. Is it a reasonable measure of team's ability? Is it more important for teams to win games, or to schedule strong opponents? These are all good questions, but for this problem, your task is more straightforward: given a schedule of games, can you calculate every team's RPI?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the number of teams N.
The next N lines each contain exactly N characters (either '0', '1', or '.') representing a schedule in the same format as the example schedule above. A '1' in row i, column j indicates team i beat team j, a '0' in row i, column j indicates team i lost to team j, and a '.' in row i, column j indicates team i never played against team j.
For each test case, output N + 1 lines. The first line should be "Case #x:" where x is the case number (starting from 1). The next N lines should contain the RPI of each team, one per line, in the same order as the schedule.
Answers with a relative or absolute error of at most 10-6 will be considered correct.
1 ≤ T ≤ 20.
If the schedule contains a '1' in row i, column j, then it contains a '0' in row j, column i.
If the schedule contains a '0' in row i, column j, then it contains a '1' in row j, column i.
If the schedule contains a '.' in row i, column j, then it contains a '.' in row j, column i.
Every team plays at least two other teams.
No two teams play each other twice.
No team plays itself.
3 ≤ N ≤ 10.
3 ≤ N ≤ 100.