Chess Competition

문제

In a chess competition, every player plays one game against every other player. The winner receives one point, the loser none. In case of a draw, both players receive half a point. When all games have been played, whoever scored the most points wins the competition. If multiple competitors are tied for the highest score, they will play a series of tie-break games to determine the winner.

For this problem we consider a competition where the games are played in arbitrary order. Based on the outcome of the games that have been played so far (which could be all, or none, or anything in between) the organizers want to determine which players can still win the competition.

입력

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with an integer n (2 ≤ n ≤ 30): the number of players.
• n lines with n characters each, describing the intermediate results. The j-th character on the i-th line gives the result of the i-th player against the j-th player:
  • ’1’ for a win,
  • ’0’ for a loss,
  • ’d’ for a draw,
  • ’.’ if this game has not been played yet,
  • ’x’ when i = j (since competitors do not play against themselves).

The intermediate results are guaranteed to be internally consistent. More formally, if the j-th character on the i-th line is a digit (’0’ or ’1’) then the i-th character on the j-th line will be the other digit. In all other cases, the j-th character on the i-th line equals the i-th character on the j-th line.

출력

Per test case:

• one line with the 1-based indices of all the players that can possibly win the competition, in increasing order, separated by spaces.

3
5
x.11d
.x1d1
00x.0
0d.x.
d01.x
7
x00111.
1x01d.d
11x1.00
000x000
0d.1xd1
0.11dxd
.d110dx
7
x00011.
1x00d.d
11x0.0.
111x111
0d.0xd.
0.10dx.
.d.0..x

1 2
1 2 3 5 6 7
4