Description

在美国，每年有 350 所学校争夺 NCAA 大学篮球锦标赛的邀请资格。由于学校众多，如何决定哪些学校应该被邀请呢？大多数队伍之间从未交手，而且有些队伍的赛程比其他队伍要艰难得多。

下面是 $4$ 支队伍 $A, B, C, D$ 的一个赛程示例：

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

每一行中的 $1$ 表示该队获胜，$0$ 表示该队失利。因此，队伍 $C$ 战胜了 $B$ 和 $D$，输给了 $A$。队伍 $A$ 战胜了 $B$ 和 $C$，但没有与 $D$ 交手。

NCAA 锦标赛委员会使用一个叫做 RPI（Ratings Percentage Index，评级百分指数）的公式来帮助排名队伍。传统上，它被定义为：

$$\text{RPI} = 0.25 \times \text{WP} + 0.50 \times \text{OWP} + 0.25 \times \text{OOWP}$$

WP、OWP 和 OOWP 对每支队伍的定义如下：

• WP（胜率）是你赢得的比赛场次占总比赛场次的比例。
  • 在示例赛程中，队伍 $A$ 的 WP = 1，队伍 $B$ 的 WP = 0，队伍 $C$ 的 WP = 2/3，队伍 $D$ 的 WP = 0.5。
• OWP（对手胜率）是你所有对手的 WP 的平均值，但首先要去掉他们与自己的比赛。
  • 例如，如果去掉与 $D$ 队的比赛，$B$ 队的 WP = 0，$C$ 队的 WP = 0.5。因此，$D$ 队的 $\text{OWP} = 0.5 \times (0 + 0.5) = 0.25$。类似地，$A$ 队的 OWP = 0.5，$B$ 队的 OWP = 0.5，$C$ 队的 OWP = 2/3。
• OOWP（对手的对手胜率）是你所有对手的 OWP 的平均值。OWP 就是上一步计算的数值。
  • 例如，$A$ 队的 $\text{OOWP} = 0.5 \times (0.5 + 2/3) = 7/12$。

综合计算，$A$ 队的 $\text{RPI} = (0.25 \times 1) + (0.5 \times 0.5) + (0.25 \times 7 / 12) = 0.6458333\dots$

关于 RPI，你可以提出一些有趣的问题。RPI 是否合理地衡量了队伍的实力？对队伍来说，赢得比赛更重要，还是安排强劲的对手更重要？

这些都是很好的问题，但对于本题，你的任务更为直接：给定一份比赛赛程，你能否计算出每支队伍的 RPI？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为队伍数 $N$。

接下来的 $N$ 行，每行包含恰好 $N$ 个字符（'0'、'1' 或 '.'），表示赛程，格式与上面的示例相同。第 $i$ 行第 $j$ 列的 '1' 表示队伍 $i$ 战胜了队伍 $j$，'0' 表示队伍 $i$ 输给了队伍 $j$，'.' 表示队伍 $i$ 没有与队伍 $j$ 交手。

Output Format

对于每组测试数据，输出 $N+1$ 行。第一行为 "Case #x:"，其中 $x$ 是测试编号（从 1 开始）。接下来的 $N$ 行，每行输出一支队伍的 RPI，顺序与输入赛程一致。

只要相对或绝对误差不超过 $10^{-6}$ 的答案都将被判为正确。

2
3
.10
0.1
10.
4
.11.
0.00
01.1
.10.

Case #1:
0.5
0.5
0.5
Case #2:
0.645833333333
0.368055555556
0.604166666667
0.395833333333

Hint

数据范围

• $1 \leq T \leq 20$。
• 如果赛程中第 $i$ 行第 $j$ 列为 '1'，则第 $j$ 行第 $i$ 列为 '0'。
• 如果赛程中第 $i$ 行第 $j$ 列为 '0'，则第 $j$ 行第 $i$ 列为 '1'。
• 如果赛程中第 $i$ 行第 $j$ 列为 '.'，则第 $j$ 行第 $i$ 列也为 '.'。
• 每支队伍至少与另外两支队伍比赛过。
• 没有两支队伍之间会比赛两次。
• 没有队伍与自己比赛。

小数据范围（8 分，测试点 1 - 可见）

• $3 \leq N \leq 10$。
• 时间限制：3 秒。

大数据范围（12 分，测试点 2 - 隐藏）

• $3 \leq N \leq 100$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译