싱글 엘리미네이션

싱글 엘리미네이션은 테니스 메이저 대회, 미국 대학 농구 토너먼트, 대학 미식축구 플레이오프, 여러 올림픽 종목에서 쓰는 대진 방식이다. 참가자 수 $n$이 2의 거듭제곱일 때 가장 깔끔하게 맞아떨어진다. 각 라운드에서 남은 선수를 둘씩 짝지어 경기를 치르고, 진 선수는 모두 탈락하고 이긴 선수만 다음 라운드에 올라간다. $\log_2 n$번의 라운드가 끝나면 한 명이 남고, 그 선수가 우승한다.

모든 상대를 이기는 선수가 있으면 그 선수가 언제나 우승한다. 선수마다 유독 상대하기 까다로운 선수가 하나 이상 있을 때부터 상황이 재미있어진다. 운이 나빠 그런 상대를 일찍 만난 선수는 탈락하고, 나중에 그 선수에게 졌을 다른 선수가 이득을 본다. 그래서 각 라운드에서 누가 누구와 붙을지 정하는 권한은 원하는 선수를 우승시키는 데 쓸모가 크다.

선수 16명이 참가한다. 두 선수가 붙으면 누가 이기는지는 모든 쌍에 대해 미리 정해져 있고, 결과는 항상 그대로 나온다. 1라운드 대진을 짠 다음, 2라운드에서는 1라운드 승자끼리 원하는 대로 짝을 지을 수 있다. 3라운드와 4라운드도 마찬가지다. 어떤 선수에게 가장 유리하게 대진을 짰을 때 그 선수가 우승한다면, 그 선수는 우승 가능성이 있다. 우승 가능성이 있는 선수를 모두 찾아라.

첫 줄에 데이터 세트의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 세트가 다음 형식으로 주어진다.

각 데이터 세트는 16개의 줄로 이루어지고, 각 줄에는 16개의 수 $a_{i,j} \in \{0, 1\}$이 주어진다. $a_{i,j} = 1$이면 $i$번 선수와 $j$번 선수가 붙었을 때 $i$번 선수가 이기고, $a_{i,j} = 0$이면 $j$번 선수가 이긴다. 서로 다른 $i$와 $j$에 대해 $a_{i,j}$와 $a_{j,i}$ 중 정확히 하나만 1이다. $i$번 선수가 자기 자신과 붙는 일은 없으므로 $a_{i,i}$의 값은 아무 의미가 없다. 입력을 읽기 편하도록 넣어 둔 값이다.

각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 세트의 번호이고 1부터 센다. 그다음 줄에 대진을 가장 유리하게 짰을 때 우승할 수 있는 선수의 번호를 증가하는 순서로, 공백 하나로 구분해 한 줄에 모두 출력한다. 각 데이터 세트를 출력한 뒤에는 빈 줄을 하나 출력한다.