311281: CF1965A. Everything Nim

A. Everything Nimtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob are playing a game on $n$ piles of stones. On each player's turn, they select a positive integer $k$ that is at most the size of the smallest nonempty pile and remove $k$ stones from each nonempty pile at once. The first player who is unable to make a move (because all piles are empty) loses.

Given that Alice goes first, who will win the game if both players play optimally?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 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 number of piles in the game.

The next line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the initial number of stones in the $i$-th pile.

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

Output

For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print "Alice", otherwise print "Bob" (without quotes).

ExampleInput

7
5
3 3 3 3 3
2
1 7
7
1 3 9 7 4 2 100
3
1 2 3
6
2 1 3 4 2 4
8
5 7 2 9 6 3 3 2
1
1000000000

Output

Alice
Bob
Alice
Alice
Bob
Alice
Alice

Note

In the first test case, Alice can win by choosing $k=3$ on her first turn, which will empty all of the piles at once.

In the second test case, Alice must choose $k=1$ on her first turn since there is a pile of size $1$, so Bob can win on the next turn by choosing $k=6$.

题目大意：
Alice和Bob在玩一个游戏，游戏中有n堆石子。每次轮到一个玩家时，他们可以选取一个正整数k（k不超过最小的非空堆的石子数），然后从每个非空堆中一次性移除k个石子。当所有堆都为空时，无法进行操作的玩家将输掉游戏。假设Alice和Bob都采取最优策略，问谁会赢得游戏。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示游戏中的堆数。
接下来的一行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），分别表示每堆石子的初始数量。
所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一行，包含获胜者的名字。如果Alice获胜，输出"Alice"，否则输出"Bob"。

示例：
输入：
7
5
3 3 3 3 3
2
1 7
7
1 3 9 7 4 2 100
3
1 2 3
6
2 1 3 4 2 4
8
5 7 2 9 6 3 3 2
1
1000000000

输出：
Alice
Bob
Alice
Alice
Bob
Alice
Alice

注意：
在第一个测试用例中，Alice可以在第一次操作时选择k=3，一次性清空所有堆。
在第二个测试用例中，Alice必须在第一次操作时选择k=1，因为有一堆大小为1的石子，所以Bob可以在下一次操作时选择k=6并赢得游戏。题目大意： Alice和Bob在玩一个游戏，游戏中有n堆石子。每次轮到一个玩家时，他们可以选取一个正整数k（k不超过最小的非空堆的石子数），然后从每个非空堆中一次性移除k个石子。当所有堆都为空时，无法进行操作的玩家将输掉游戏。假设Alice和Bob都采取最优策略，问谁会赢得游戏。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示游戏中的堆数。 接下来的一行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），分别表示每堆石子的初始数量。 所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一行，包含获胜者的名字。如果Alice获胜，输出"Alice"，否则输出"Bob"。 示例： 输入： 7 5 3 3 3 3 3 2 1 7 7 1 3 9 7 4 2 100 3 1 2 3 6 2 1 3 4 2 4 8 5 7 2 9 6 3 3 2 1 1000000000 输出： Alice Bob Alice Alice Bob Alice Alice 注意： 在第一个测试用例中，Alice可以在第一次操作时选择k=3，一次性清空所有堆。 在第二个测试用例中，Alice必须在第一次操作时选择k=1，因为有一堆大小为1的石子，所以Bob可以在下一次操作时选择k=6并赢得游戏。