Problem Description

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

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

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 length $m$. The two players take turns, and on each turn they must choose one of the following operations:

• Choose an index $i$ $(1\le i<m)$ such that $a_i>a_{i+1}$, and swap $a_i$ and $a_{i+1}$.
• Choose an index $i$ $(1\le i<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, if the current permutation is $[2,3,4,1]$, you may delete the adjacent $2,3$, leaving $[4,1]$; after renumbering, the permutation becomes $[2,1]$.

When a player cannot make any move, that player loses. Assuming both Alice and Bob play optimally, determine the winner.

Input Format

This problem has 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\le 5000)$.
• The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, and 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 Format

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

5
1
1
2
1 2
2
2 1
4
2 4 1 3
5
5 1 4 2 3

Bob
Alice
Bob
Alice
Bob

Hint

Translated by ChatGPT 5