Grand Game Tournament

The "Grand Game Tournament" is the most famous game competition in the world.

Every player plays exactly one 1-vs-1 game against every other player. In each game the winner earns 1 point and the loser earns 0 points; if the game is a draw, both players earn 0.5 points. After all games are finished, the player with the highest score is the champion. If several players are tied for the highest score, they play tie-break games among themselves until a single champion remains. Therefore any player whose final score equals the maximum score has a chance to win the tournament.

The tournament is still in progress and only some of the games have been played. For each player, if the not-yet-played games can be completed in some way so that this player ends up with the maximum final score (ties for first included), then that player "can win" the tournament. Find every player who can win.

The first line contains the number of test cases $T$ ($T \le 100$).

Each test case is given as follows.

• The first line contains the number of players $n$ ($2 \le n \le 30$).
• The next $n$ lines give the current partial results as an $n \times n$ grid. The $j$-th character of the $i$-th line is the result of the game between player $i$ and player $j$.
  • 1 : player $i$ won
  • 0 : player $i$ lost
  • d : draw
  • . : the game has not been played yet
  • x : $i = j$ (a player does not play against themselves)

The partial results are consistent: if row $i$ column $j$ is 1, then row $j$ column $i$ is 0, and vice versa; a cell that is d or . equals the cell in the mirrored position.

For each test case, print on one line the numbers (1-indexed) of all players who can win, in ascending order, separated by spaces.