Problem Description

You are given $n$ piles of stones. The $i$-th pile contains $a_i$ stones, and it is guaranteed that $\bm{a_i}$ are all distinct.

Alice and Bob take turns performing one of the following two operations, and after the operation they remove any pile whose number of stones becomes $0$. Alice moves first. The player who cannot make a move loses.

• Take one stone from every pile.
• Remove the pile with the smallest number of stones.

Assuming both players play optimally, determine who will win. You need to answer $T$ queries.

Input Format

This problem contains multiple queries in a single test case.

The first line contains a positive integer $T$, the number of queries.

For each query: the first line contains a positive integer $n$, the number of piles. The second line contains $n$ positive integers, where the $i$-th integer represents $a_i$.

Output Format

For each query, output one line containing Alice or Bob, indicating who will win.

3
1
7
3
6 7 3
4
2 8 5 6

Alice
Bob
Alice

Hint

This problem uses bundled tests.

For $100\%$ of the testdata:

• $1 \le T \le 2 \times 10^5$；
• $1 \le n \le 2 \times 10^5$；
• $1 \le a_i \le 10^9$；
• $a_i$ are pairwise distinct；
• $\sum n \le 2 \times 10^5$。

The detailed subtask distribution is as follows:

Translated by ChatGPT 5