Alice and Bob have an array of integers. They decide to play a game with the array. In one move,
Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. If a player can't make any move, he/she loses. Who will win if both play optimally?
The first line of the input contains one integer , the number of test cases.
In each test case, the first line contains an integer , the number of elements in .
The next line contains integers , where is the element of .
For each test case, print the name of the winner in a single line. If Alice wins, print “Alice” (without quotes) otherwise print “Bob” (without quotes).
3 3 0 0 0 2 0 5 3 2 0 6
Bob Alice Bob
In the case, Alice can’t make the first move. So, Bob wins.
Login to submit
If the count of non-zero elements is odd, Alice wins. Otherwise, Bob wins. Why? Find out yourself.