Two players (numbered and ) are playing a game of Tower Breakers! The rules of the game are as follows:
Given the value of and the respective height values for all towers, can you determine who will win, assuming both players always move optimally? If the first player wins, print ; otherwise, print .
The first line contains an integer, , denoting the number of test cases.
The subsequent lines define the test cases. Each test case is described by two lines:
For each test case, print a single integer denoting the winner (i.e., either or ) on a new line.
1 2 3
In the first test case, the first player simply breaks down the second tower of height into two towers of height and wins.
In the second test case, there are only two possible moves:
Whichever move player makes, player can make the other move and win the game.