Alice and Bob are playing a game on a string of length consisting of characters ‘0’ and ‘1’. They take alternating turns. Alice moves first.
In each turn, a player selects three different indices , and such that , and and change to , to and to . In other words, the player inverts the characters , and . The game ends when the string becomes a palindrome or there is no possible move. If the current player has no valid move, he (or she) loses the game.
Who will win the game if both players play optimally?
A palindrome is a string that reads the same backward as forward, for example, strings "0", "010", "10101", "110011" are palindromes, but strings "01", "01101", "1101" are not.
The first line of the input contains a single integer the number of test cases.
The first line of each test case contains an integer the length of the string .
The second line of each test case contains the string consisting of the characters and .
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, print the answer in a single line.
If Alice wins, print Alice. Otherwise, print Bob.
5 4 1000 6 100101 8 01001000 4 1001 2 01
Alice Alice Bob Bob Bob
In the first test case, Alice can select , and . The string becomes after his move which is a palindrome. The game ends after the move and Bob can’t make her move.
In the second test case, Alice can select , and .
In the third test case, all strategies of Alice lead winning of Bob.
In the fourth test case, Alice can’t move because the string is already palindrome and the game ends before Alice’s move.
In the fifth test case, Alice has no valid move. So, Bob wins.