J. Just another Sorting Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
According to the problem statement, Bob is the one who lives longer.
—Hotpot-chicken

Jessica is a master of sorting algorithms, proficient in selection sort, insertion sort, bubble sort, and many others. Therefore, she decided to host a sorting competition.

The competition takes place on a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$, with two participants: Alice and Bob. The two players take turns performing operations, with the first player being decided by a coin toss. If the sequence is in ascending order after any player's turn, Alice wins immediately. If Alice cannot win within a finite number of turns, Bob is considered the winner.

On Alice's turn, she can choose any two positions $$$i,j$$$ ($$$i \neq j, 1 \leq i,j \leq n$$$) in the permutation and swap $$$p_i$$$ and $$$p_j$$$. On Bob's turn, he can select two adjacent positions $$$i,i+1$$$ ($$$1 \leq i \lt n$$$) and swap $$$p_i$$$ and $$$p_{i+1}$$$. Neither player is allowed to skip their turn.

Given the permutation $$$p$$$ and the name of the player who operates first, determine who will win the game if both players play optimally.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is a $$$4$$$ in the array).

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and a string $$$s$$$ ($$$s \in \{$$$Alice, Bob$$$\}$$$), representing the length of the permutation and the name of the player who operates first.

The second line contains $$$n$$$ integers $$$p_1, p_2, \cdots, p_n$$$ ($$$1 \leq p_i \leq n$$$), representing the permutation $$$p$$$. It is guaranteed that there is at least one position $$$i$$$ such that $$$p_i \neq i$$$.

For each test file, it is guaranteed that the sum of all $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output one line containing the winner's name. If Alice wins, print "Alice"; otherwise, print "Bob".

Example
Input
3
2 Alice
2 1
3 Bob
1 3 2
10 Bob
1 2 3 4 5 6 7 8 10 9
Output
Alice
Bob
Bob