M. 巴巴博弈
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice 和 Bob 正在玩一个游戏，游戏开始时，一共有 $$$n$$$ 堆石子，每堆石子的数量分别为 $$$a_1,a_2,\dots,a_n$$$，Alice 和 Bob 轮流做以下操作：

  • 选择若干堆石子，取走其中一颗石子。
  • 如果本轮取完剩下所有石子，则获胜。

假设 Alice 和 Bob 每轮操作均采用最优策略的情况下，假设 Alice 先手，她想知道能否获胜。

Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^4)$$$，表示测试组数。

接下来的 $$$T$$$ 组测试，每组测试个数如下：

  • 第一行输入一个正整数 $$$n\ (1\le n\le 5\times 10^5)$$$，表示石子堆数量。
  • 第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$$$，表示每堆石子的数量。

此外，数据保证所有测试组 $$$n$$$ 的总和不超过 $$$5\times 10^5$$$。

Output

对于每组测试，输出格式如下：

  • 如果 Alice 可以获胜，则输出 Alice，否则输出 Bob。
Example
Input
5
1
4
2
1 2
3
11 45 14
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
9
9 9 8 2 4 4 3 5 3
Output
Bob
Alice
Alice
Bob
Alice