RPI

미국에서는 매년 350개의 학교가 NCAA 대학 농구 토너먼트 초청권을 두고 경쟁한다. 학교가 이렇게 많은데, 어느 학교를 초청해야 할지는 어떻게 결정할까? 대부분의 팀은 서로 경기를 치르지 않으며, 일부 팀은 다른 팀보다 훨씬 어려운 경기 일정을 소화한다.

다음은 A, B, C, D라는 이름을 가진 4개 팀의 경기 일정 예시이다.

|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)라는 공식을 사용한다. 전통적으로 이 공식은 다음과 같이 정의되어 왔다.

RPI = 0.25 * WP + 0.50 * OWP + 0.25 * 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 팀의 OWP = 0.5 * (0 + 0.5) = 0.25이다. 마찬가지로 A 팀의 OWP = 0.5, B 팀의 OWP = 0.5, C 팀의 OWP = 2/3이다.

• OOWP (상대 팀의 상대 팀 승률)는 모든 상대 팀의 OWP 평균이다. OWP는 바로 이전 단계에서 계산한 수치이다. 예를 들어 A 팀의 OOWP = 0.5 * (0.5 + 2/3) = 7/12이다.

이 모든 것을 종합하면 A 팀의 RPI = (0.25 * 1) + (0.5 * 0.5) + (0.25 * 7 / 12) = 0.6458333...임을 알 수 있다.

RPI에 관해서는 꽤 흥미로운 질문들을 던질 수 있다. 이것은 팀의 실력을 합리적으로 측정하는 척도인가? 팀에는 경기에서 승리하는 것과 강한 상대와 경기하도록 일정을 잡는 것 중 어느 쪽이 더 중요한가? 모두 좋은 질문이지만, 이 문제에서 해야 할 일은 더 단순하다. 경기 일정이 주어졌을 때 모든 팀의 RPI를 계산할 수 있는가?

제한

1 ≤ T ≤ 20. 경기 일정의 i행 j열에 '1'가 있으면 j행 i열에는 '0'가 있다. 경기 일정의 i행 j열에 '0'가 있으면 j행 i열에는 '1'가 있다. 경기 일정의 i행 j열에 '.'가 있으면 j행 i열에도 '.'가 있다. 모든 팀은 적어도 서로 다른 두 팀과 경기한다. 어떤 두 팀도 서로 두 번 경기하지 않는다. 어떤 팀도 자기 자신과 경기하지 않는다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 10. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 100. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 팀의 수 N이 담긴 한 줄로 시작한다.

다음 N개의 줄에는 위의 예시 경기 일정과 같은 형식으로 경기 일정을 나타내는 정확히 N개의 문자('0', '1', 또는 '.')가 각각 주어진다. i행 j열의 '1'는 i 팀이 j 팀을 이겼음을 나타내고, i행 j열의 '0'는 i 팀이 j 팀에게 졌음을 나타내며, i행 j열의 '.'는 i 팀이 j 팀과 경기한 적이 없음을 나타낸다.

각 테스트 케이스마다 N + 1개의 줄을 출력한다. 첫 번째 줄에는 "Case #x:"를 출력하며, 여기서 x는 테스트 케이스 번호이다(번호는 1부터 시작한다). 다음 N개의 줄에는 경기 일정과 같은 순서로 각 팀의 RPI를 한 줄에 하나씩 출력한다.

상대 오차 또는 절대 오차가 최대 10^{-6}인 답은 정답으로 간주한다.