토너먼트 역전

컨코르디아 지역에서는 유명한 기술 대학 연합의 팀들이 매년 월리볼 토너먼트를 연다. 여러분의 대학인 Beaver Valley Institute of Mines and Telecommunication Tech도 이 대회에 참가하는 자랑스러운 기관이다. 대회 방식은 간단하다. 8개 팀을 4쌍으로 나눠 8강전을 치른다. 8강전의 승자는 2쌍으로 나뉘어 준결승 두 경기를 치른다. 마지막으로 준결승의 승자가 결승에서 만난다.

올해는 대학 간 연합이 곧 해체될 예정이라 특별하다. 모교는 이름의 일부를 잃게 되고, 이번 대회는 다시는 되찾을 수 없는 트로피를 차지할 마지막 기회다. 우리 대학은 늘 페어플레이를 지켜 왔고 부정행위는 결코 하지 않는다. 그렇다면 팀들의 대진 순서를 유리하게 정해서 행운이 조금이라도 도와준다면 어떨까?

스포츠국은 방대한 통계를 모아 두었다. 연합의 비교적 짧은 역사 동안 각 팀이 다른 팀을 상대로 몇 번 이겼는지 알 수 있다. 이 기록이 개별 경기의 결과 확률을 준다고 가정한다. 팀 $p$가 팀 $q$를 $n$번 이겼고 팀 $q$가 팀 $p$를 $m$번 이겼다면, $p$와 $q$의 경기에서 $p$가 이길 확률은 $\frac{n}{n+m}$이고 $q$가 이길 확률은 $\frac{m}{n+m}$이다. 무승부는 없다. 과거에 $p$가 $q$를 한 번도 이기지 못했다면, 대회에서도 $p$가 이길 확률은 0이다. 모든 팀 쌍이 최소 한 번은 맞붙었으므로 확률은 항상 정의된다.

이 확률 모델에 따를 때, 우리 팀이 대회 전체에서 우승할 확률을 최대로 만드는 팀 순서는 무엇인가?

입력 파일에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 $c$ 하나가 주어진다. 각 테스트 케이스는 공백으로 구분된 정수 8개씩 8줄로 이루어진다. $1 \leq i, j \leq 8$에 대해, $i$번째 줄의 $j$번째 정수는 팀 $i-1$이 팀 $j-1$을 상대로 이긴 경기 수다. 각 정수는 0 이상 5 이하이다. 대각선 위의 정수는 항상 0이다. 모든 팀 쌍이 최소 한 번은 경기했으므로, $i \neq j$이면 $i$번째 줄의 $j$번째 정수나 $j$번째 줄의 $i$번째 정수 중 하나는 0이 아니다. 우리 대학은 입력 순서에서 항상 첫 번째 대학이다.

각 테스트 케이스마다 한 줄에 실수 하나와 공백으로 구분된 정수 8개를 출력한다. 실수는 우리 대학이 대회에서 우승할 최대 확률을 소수점 아래 정확히 5자리로 반올림한 값이다. 정수 8개는 이 확률을 달성하는 팀 순서를 뜻한다. 경기는 위 그림의 순서대로 진행되고 각 경기는 확률 모델에 따라 결정된다고 가정한다. 여러 배치가 같은 확률을 주면 사전식으로 가장 작은 것을 출력한다.