Turja and Akash are playing an interesting game. Initially a pile of N stones is given to them. Each of them will make their move alternatively. In each move one should remove some stones from the pile and give the pile to other person. Let X be the number of stones in the pile when a move starts (Initially X = N), Y be the number of stones removed in a move by any player and K is a given constant. One has to remove at least one and at most X stones in a move. That means 1<=Y<=X should hold for every move. To make this game interesting another constraint on choosing Y is given. Y should be a coprime with K and bitwise AND between Y and K should be a non-zero value . So, GCD(Y,K) = 1 and (Y&K) > 0 should hold in every move to remove Y stones. After removing Y stones pile size(number of stones in the pile) will be decremented by Y. The player who can't make any move first loses.
Since Turja is senior he will always make the first move. If both of them play optimally, can Turja use the advantage of being senior and win the game? or Akash will surprise him by winning the game?
At first, you are given an integer T (T<=150), which is the number of test cases. For each case, you will be given two positive integers N & K that are the number of initial stones at pile and a constant (1 <= N,K <= 500).
For each test case print Turja if Turja wins the game or Akash if Akash wins the game. See sample I/O for better understanding.
2 3 5 2 2
Login to submit