Alice and Bob are playing game on array $a$ initially containing $n$ positive integers, with Alice going first.

On each player's turn, if $a$ is non-decreasing$^{\text{∗}}$, the game immediately ends. Otherwise, the player can choose an element $x$ from the array and positive integers $1 \lt y,z \lt x$ such that $x=yz$ and replace $x$ in the array with two elements $y$ and $z$ (in any order at the original location of $x$). If no such move is possible, the game ends.

Once the game ends, if $a$ is non-decreasing, then Bob wins. Otherwise, Alice wins. Determine who will win the game if both players play optimally.

The first line contains an integer $t$ ($1 \leq t \leq 10^4$), the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$).

The sum of $n$ over all test cases does not exceed $10^5$.

For each test case, output a line containing "Alice" if Alice wins or "Bob" if Bob wins. The grader is case-sensitive.