311289: CF1966C. Everything Nim

C. 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先手，如果两位玩家都采取最优策略，谁会赢得游戏？

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示游戏中的堆数。
- 每个测试用例的下一行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），其中a_i是第i堆石头的初始数量。
- 保证所有测试用例的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和Bob在玩一个游戏，游戏中有n堆石头。每位玩家在他们的回合选择一个正整数k，k的值不超过最小的非空堆的大小，并且同时从每个非空堆中移除k块石头。当所有堆都为空时，无法进行移动的玩家输掉游戏。假设Alice先手，如果两位玩家都采取最优策略，谁会赢得游戏？ 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示游戏中的堆数。 - 每个测试用例的下一行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），其中a_i是第i堆石头的初始数量。 - 保证所有测试用例的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 ```