D. Duel of Ten
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob play a Duel of Ten on an array $$$a$$$ of length $$$n$$$ ($$$\boldsymbol{-10^9} \leq a_i \leq 10^9$$$). They take turns making moves, with Alice going first. The rules of "Duel-of-Ten" are as follows:

  • Let the current length of the array $$$a$$$ be $$$m$$$ (initially $$$m = n$$$).
  • On Alice's turn, Alice chooses two distinct indices $$$x$$$ and $$$y$$$ ($$$1\leq x \lt y \leq m$$$) and removes elements $$$a_x$$$ and $$$a_y$$$ from $$$a$$$, then inserts $$$\min(a_x, a_y)$$$ into $$$a$$$.
  • On Bob's turn, Bob chooses two distinct indices $$$x$$$ and $$$y$$$ ($$$1\leq x \lt y \leq m$$$) and removes elements $$$a_x$$$ and $$$a_y$$$ from $$$a$$$, then inserts $$$\max(a_x, a_y)$$$ into $$$a$$$.
Thus, each move decreases the length of the array by $$$1$$$.

The game ends when the array $$$a$$$ contains only one element. If the remaining element has an absolute value less than 10, Alice wins. Otherwise, Bob wins.

Given an array $$$a$$$, determine who wins if both players play optimally.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t \leq 10^3$$$) — the number of test cases. For each test case,

  • The first line contains a single integer $$$n$$$ ($$$2\leq n \leq 2\times 10^5$$$) — the length of the array $$$a$$$.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots , a_n$$$ ($$$\boldsymbol{-10^9}\leq a_i \leq 10^9$$$).
The sum of $$$n$$$ over all test cases will not exceed $$$2\times 10^5$$$.
Output

$$$t$$$ lines. For each test case, output Alice if Alice wins, and Bob otherwise, assuming both players play optimally.

Example
Input
2
4
1 10 1 10
4
1 -10 1 -10
Output
Alice
Bob
Note

There are 2 test cases. For each test case, we show one possible sequence of moves that ends with the stated winner. These sequences are included only to illustrate the rules; the players do not necessarily play optimally.

  • For the first test case, one possible sequence of moves that leads to Alice winning is as follows:
    • The array is initially $$$a=[1,10,1,10]$$$.
    • Alice removes $$$1$$$ and $$$10$$$, and inserts $$$\min(1,10)=1$$$ into $$$a$$$. The new array $$$a$$$ is $$$[1,1,10]$$$.
    • Bob removes $$$1$$$ and $$$10$$$, and inserts $$$\max(1,10) = 10$$$ into $$$a$$$. The new array $$$a$$$ is $$$[1,10]$$$.
    • Alice then chooses $$$1$$$, $$$10$$$, and inserts $$$\min(1, 10) = 1$$$ into $$$a$$$. The new array $$$a$$$ is $$$[1]$$$.
    Since $$$|1| \lt 10$$$, Alice wins.
  • For the second test case, one possible sequence of moves that leads to Bob winning is as follows:
    • The array is initially $$$a = [1,-10, 1, -10]$$$.
    • Alice removes $$$1$$$ and $$$-10$$$, and inserts $$$\min(1,-10) = -10$$$ into $$$a$$$. The new array $$$a$$$ is $$$[-10, 1, -10]$$$.
    • Bob removes $$$1$$$ and $$$-10$$$, and inserts $$$\max(1,-10) = 1$$$ into $$$a$$$. The new array $$$a$$$ is $$$[1, -10]$$$.
    • Alice removes $$$1$$$ and $$$-10$$$ and inserts $$$\min(1, -10) = -10$$$ into $$$a$$$. The new array $$$a$$$ is $$$[-10]$$$.
    Since $$$|-10| = 10$$$, Bob wins.