A and B are playing a game. There are N stacks in front of them, each made up of Ai stones. The game is played in turns and in each turn, a player has to either pick up one stone or one full stack. That stone or stack is then eliminated from the game. The player who picks up the last stone loses. Given that both play optimally and A goes first, find out who will win.
Input:
- The first line has an integer T for the number of test cases. Description of T test cases follow.
- Each test case contains two lines. The first line contains N, the total number of stacks and the second line contains N space-separated integers Ai, denoting the number of stones in the ith stack.
Output:
For each test case print a single line containing either A or B according to who will win the game.
Constraints:
1≤T≤200
1≤N≤104
1≤Ai≤1010 for scoring 50
1≤Ai≤1022 for scoring 100
Problem Author: Rohit Agarwal
In the first case, there is only one stack. So the players can not pick up the full stack as it will result in a loss. So they will only pick a single stone on their turn. A will pick up the third stone, B will pick the second and A will have to pick up the last one. So B wins.
In the second case, there are two stacks. A can pick the stack containing four stones. Now only a three stone stack is left and it is B's turn. B will pick up the third stone, A will pick up second and B will pick up the last stone. So A has a guaranteed win.
