Two players are playing a game on a chessboard. The rules of the game are as follows:
The game starts with coins located at one or more coordinates on the board (a single cell may contain more than one coin). The coordinate of the upper left cell is , and the coordinate of the lower right cell is .
In each move, a player must move a single coin from some cell to one of the following locations:
Note: The coin must remain inside the confines of the board.
The players move in alternating turns. The first player who is unable to make a move loses the game.
The figure below shows all four possible moves:
Note: While the figure shows a board, this game is played on a board.
Given the value of and the initial coordinate(s) of coins, determine which player will win the game. Assume both players always move optimally.
The first line contains an integer, , denoting the number of test cases.
Each test case is defined as follows over the subsequent lines:
The first line contains an integer, , denoting the number of coins on the board.
Each line (where ) of the subsequent lines contains space-separated integers describing the respective values of and of the coordinate where coin is located.
Note: Recall that a cell can have more than one coin (i.e., any cell can have to coins in it at any given time).
, where .
On a new line for each test case, print if the first player is the winner; otherwise, print .