B. Vanishing Inversions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on a permutation, with Alice moving first.

A sequence of length $$$n$$$ is called a permutation if and only if each integer from $$$1,2,\dots,n$$$ appears exactly once in the sequence.

Initially, a permutation $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$ is given. At any moment during the game, the current sequence is always a permutation of some length $$$m$$$. Alice and Bob take turns performing exactly one of the following two operations:

- Choose an index $$$i$$$ $$$(1\le i \lt m)$$$ such that $$$a_i \gt a_{i+1}$$$, and swap $$$a_i$$$ and $$$a_{i+1}$$$.

- Choose an index $$$i$$$ $$$(1\le i \lt m)$$$ such that $$$a_{i+1}=a_i+1$$$, and delete $$$a_i$$$ and $$$a_{i+1}$$$. Then renumber the remaining elements according to their relative order: the $$$k$$$-th smallest remaining element is renumbered as $$$k$$$, so that the remaining sequence becomes a permutation again.

For example, suppose the current permutation is $$$[2,3,4,1]$$$. The adjacent elements $$$2$$$ and $$$3$$$ can be deleted, leaving $$$[4,1]$$$; after renumbering, the permutation becomes $$$[2,1]$$$.

A player who cannot perform any operation loses the game. Assuming that both Alice and Bob play optimally, determine the winner.

Input

Each test contains multiple test cases.

The first line contains an integer $$$T$$$ $$$(1\le T\le 5000)$$$, the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ $$$(1\le n\le5000)$$$.
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. It is guaranteed that $$$a$$$ is a permutation of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output Alice if Alice wins; otherwise, output Bob.

Example
Input
5
1
1
2
1 2
2
2 1
4
2 4 1 3
5
5 1 4 2 3
Output
Bob
Alice
Bob
Alice
Bob