Alice and Bob Stone Game

Two players, Alice and Bob, are playing a game with n piles of stones. The i-th pile initially contains \(a_i\) stones, and it is guaranteed that all \(a_i\)'s are distinct.

The players alternate turns with Alice moving first. On each turn the current player must perform exactly one of the following operations. After the operation, any pile whose number of stones becomes zero is removed from the game. A player who is unable to make a move loses.

• Operation 1: Remove one stone from every pile. (This move is allowed only if the pile with the minimum stones, say \(a_1\) after sorting in increasing order, is greater than 1.)
• Operation 2: Remove the pile with the minimum number of stones.

Under optimal play, determine the winner. You need to answer T independent queries.

Hint: Let \(k\) be the number of piles (when the piles are considered in increasing order) that have exactly one stone consecutively from the beginning. If all piles contain one stone (i.e. \(k=n\)), then the winner is decided by the parity of \(n\): Alice wins if \(n\) is odd and Bob wins if \(n\) is even. Otherwise, if \(k < n\), then the answer is determined by \(k\): Alice wins if \(k\) is even and Bob wins if \(k\) is odd.

inputFormat

The first line contains an integer T (\(1 \le T \le 10^4\)), the number of test cases. The descriptions of the test cases follow.

For each test case:

• The first line contains an integer n (\(1 \le n \le 10^5\)) — the number of stone piles.
• The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)), representing the number of stones in each pile. It is guaranteed that all \(a_i\)'s are distinct.

The total sum of n over all test cases does not exceed \(10^5\).

outputFormat

For each test case, output a single line containing either Alice or Bob — the winner under optimal play.

sample

1
1
1

Alice