C. Crushing the Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are given an array $$$a$$$ consisting of $$$n$$$ integers. They decided to play a game on it.

The players take turns making moves, with Alice moving first. In each move, the player must choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) such that all of the following conditions are satisfied:

  • $$$l = 1$$$ or $$$a_l \ne a_{l-1}$$$;
  • $$$a_i = a_{i-1}$$$ for all $$$l \lt i \le r$$$;
  • $$$r = n$$$ or $$$a_r \ne a_{r+1}$$$.

After that, the segment $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is deleted from the array $$$a$$$. The player who cannot make a move loses.

Furthermore, Alice has the ability to arbitrarily rearrange the array before starting the game. Determine who wins, if Alice can rearrange the array before making the first move, and assuming that both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single line containing the winner of the game assuming both players play optimally.

Output Alice if Alice wins the game, otherwise output Bob.

Example
Input
3
5
1 2 1 2 3
2
1 2
9
9 9 8 2 4 4 3 5 3
Output
Alice
Bob
Alice
Note

For the first testcase, Alice can rearrange the array to $$$[1, 1, 2, 2, 3]$$$.