천하제일 게임 대회

"천하제일 게임 대회"는 세계에서 가장 유명한 게임 대회이다.

모든 선수는 다른 모든 선수와 정확히 한 번씩 1:1 경기를 치른다. 각 경기에서 이긴 선수는 1점을, 진 선수는 0점을 얻고, 비기면 두 선수 모두 0.5점을 얻는다. 모든 경기가 끝나면 점수가 가장 높은 선수가 우승자가 된다. 점수가 가장 높은 선수가 여러 명이면, 우승자가 한 명 남을 때까지 그 선수들끼리 타이브레이크 경기를 치른다. 따라서 최종 점수가 최댓값과 같은 선수라면 누구나 우승할 가능성이 있다.

대회는 아직 진행 중이며 일부 경기만 끝난 상태이다. 각 선수에 대해, 아직 치르지 않은 경기들의 결과를 적절히 정하여 그 선수가 최종적으로 최고 점수(공동 1위 포함)에 도달하도록 만들 수 있으면 그 선수는 "우승할 수 있는 선수"이다. 우승할 수 있는 모든 선수를 찾아라.

첫 번째 줄에 테스트 케이스의 수 $T$ ($T \le 100$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 선수의 수 $n$ ($2 \le n \le 30$)이 주어진다.
• 이어지는 $n$개의 줄에 현재까지의 중간 결과가 $n \times n$ 격자로 주어진다. $i$번째 줄의 $j$번째 문자는 $i$번 선수와 $j$번 선수의 경기 결과를 나타낸다.
  • 1 : $i$번 선수가 이김
  • 0 : $i$번 선수가 짐
  • d : 비김
  • . : 아직 경기를 치르지 않음
  • x : $i = j$ (자기 자신과는 경기하지 않음)

중간 결과는 서로 모순되지 않는다. 즉 $i$행 $j$열이 1이면 $j$행 $i$열은 0이고 그 반대도 성립하며, d 또는 .인 칸은 대칭 위치의 칸과 값이 같다.

각 테스트 케이스마다 한 줄에, 우승할 수 있는 모든 선수의 번호(1-indexed)를 오름차순으로 공백으로 구분하여 출력한다.