Alice and Bob are employees of Dunder Mifflin. They are playing a game with a binary string of length N. Alice always goes first, followed by Bob, and they take turns making moves.
Game Rules:
On each turn, the player must place either a "&" (AND) or "|" (OR) between two adjacent characters in the string. The final expression is evaluated from left to right, following the placement of operators. Alice wins if the final result is 1, and Bob wins if the final result is 0. Both play optimally, meaning they make moves to maximize their chances of winning. Given the binary string S, determine who will win the game.
Note: The output will be evaluated in the following way: example string : 1010 after sample operations: 1 & 0 | 1 & 0 evaluation: (((1 & 0)| 1) & 0) = 0
Input Format
First line of input contains T i.e the number of testcases
Next pair of lines contains length of the string N & the string S
Constraints
1<= T <= 100 1<= N <= 10^5
Output Format
Print "ALICE" if alice can win the game or "BOB" of bob can win the game. The game will always have a winner
Sample Input 0
2
3
101
2
00
Sample Output 0
ALICE
BOB
Explanation 0
input 1: Alice will first insert a '|' bitwise operator between the second and third bit and bob will insert an '&' bitwise operator between the first and the second bit, the resultant would be 1 & 0 | 1 = 1 Alice will win
input 2: Bob will win regardless of the operation alice performs
This is the actual question. Asked in yesterday's codeUncode event!
