A and B are playing a game. in the game there is a pile of N coins. A always plays first. In a single move, a player can remove X^i coins from the pile (i>=0). It is also given that X is odd. So lets say X=3, then he can remove 1,3,9,27... and so on number of coins from the pile. Both players play optimally. The game is played in alternating turns. The player who can't remove any coins from the pile in his turn loses the game.
So for a given pile size N and X, print the name of winner.
Input Format
First line contain a integer T denoting the number of testcases. Next T lines contains 2 integers N and X for every test case.
Output Format
Print the answer to every test case in a new line.
Constraints
1<= N,X,T <= 10^5
1st test case - A can remove only 1 coin in his first move. Then B removes 1 coin in the second move. In third move, A removes one more coin. B removes the last coin remaining in the fourth move . Now the piles has 0 coins hence B wins the game.
2nd test case - A removes 3 coins in his first move and now B can't remove any coin. Hence A wins the game.
