F. Permutation Coloring Game
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game. They have a permutation $$$p$$$ of length $$$n$$$ — an array of $$$n$$$ elements in which every integer from $$$1$$$ to $$$n$$$ occurs exactly once. Initially, every element of the permutation is colored white.

The players take turns; Alice goes first. On each turn, the current player chooses between $$$1$$$ and $$$k$$$ white elements and colors all of them either red or blue. All elements chosen on the same turn must receive the same color.

The game ends when there are no white elements left. If the resulting permutation can be sorted in increasing order by swapping elements of the same color, Alice wins. Otherwise, Bob wins. Any two elements may be swapped as long as they have the same color.

Determine who wins if both players play optimally.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

  • the first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le \min(20, n)$$$) — the length of the permutation and the maximum number of elements that can be colored in one turn;
  • the second line contains $$$n$$$ pairwise distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, print Alice on a separate line if Alice wins, or Bob if Bob wins.

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