human
PYTHON3 solution for "This is an interactive problem.

ICPC Assiut Community decided to hold a unique chess contest, and you were chosen to control a queen and hunt down the hidden king, while a member of ICPC Assiut Community controls this king.

You compete on an 8×8 chessboard, the rows are numerated from top to bottom, and the columns are numerated left to right, and the cell in row x and column y is denoted as (x, y).

In one turn you can move the queen to any of the squares on the same horizontal line, vertical line, or any of the diagonals. For example, if the queen was on square (4, 5), you can move to (q_1, 5), (4, q_1), (q_1, 9-q_1), or (q_2, q_2+1) where (1 ≤ q_1 ≤ 8, q_1 ≠ 4, 1 ≤ q_2 ≤ 7, q_2 ≠ 4). Note that the queen cannot stay on its current cell. 


In one turn, the king can move "Right", "Left", "Up", "Down", "Down-Right", "Down-Left", "Up-Left", or "Up-Right" such that he doesn't get out of the board. The king cannot move into a cell that is on the same row, column or diagonal with the queen (including the position of the queen itself). For example, if the king was on square (4, 5), he can move to (4+k_1, 5+k_2) where (-1 ≤ k_1,k_2 ≤ 1, (k_1, k_2) ≠ (0, 0)). 


At the start of the game, you should place the queen at any location on the board, and this is done once per game. After that the king is secretly placed at any cell different from the queen's location. You do not know the position of the king. Then, the king and the queen take turns with the king moving first. The king moves to one of the possible directions ("Right", "Down", "Up-Left", etc.), and you are only given the direction it moves to. After that, you should move your queen by declaring the square to which your queen will move. The game follows like this until you win the game or run out of moves.

You win if the king has no valid moves. You lose if after 130 moves of the queen the king still has valid moves.

Input

The first line contains a single integer t (1 ≤ t ≤ 60) — the number of test cases.

Interaction

In each test case,...":
assistant
#Here is the Python code you requested.
 import random

N = 8

# t = 1
t = int(input())

# random.seed(2)

def under_attack(i, j):
    global queen_x, queen_y
    return i == queen_x or j == queen_y or i + j == queen_x + queen_y or i - j == queen_x - queen_y

class King:
    def __init__(self):
        self.x = random.randint(0, N - 1)
        self.y = random.randint(0, N - 1)
        print("king initiated ", self.x, self.y, flush=True)

    def move(self):
        choices = []
        for i in range(self.x - 1, self.x + 2):
            for j in range(self.y - 1, self.y + 2):
                if 0 <= i < N and 0 <= j < N and not under_attack(i, j):
                    choices += [[i, j]]
        try:
            choices.remove([self.x, self.y])
        except:
            pass
        if not choices:
            return "Done"
        choice = random.choice(choices)
        s = ""
        if choice[0] < self.x:
            s = 'Up'
        elif choice[0] > self.x:
            s = 'Down'
        if choice[0] != self.x and s:
            s += '-'
        if choice[1] < self.y:
            s += 'Left'
        elif choice[1] > self.y:
            s += 'Right'
        self.x, self.y = choice
        print("king moved ", s, self.x, self.y, flush=True)
        return s

def str_to_move(s: str):
    x, y = 0, 0
    if s.endswith('Right'):
        y += 1
    elif s.endswith('Left'):
        y -= 1
    if s.startswith('Down'):
        x += 1
    elif s.startswith('Up'):
        x -= 1
    return x, y

def get_next_king_move():
    # return str_to_move(king.move())
    return str_to_move(input())

while t > 0:
    # king = King()
    t -= 1
    queen_x, queen_y = 0, 0
    king_x, king_y = 0, 0
    possible_king_positions = [[True] * N for i in range(N)]
    knock_out = False
    while True:
        print(queen_x + 1, queen_y + 1, flush=True)
        mx, my = get_next_king_move()
        if mx == my == 0:
            knock_out = True
            break
        king_x += mx
        king_y += my
        possible_next_move = []
        for i in range(N):
      ...