F. Игра с раскрашиванием перестановки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть перестановка $$$p$$$ длины $$$n$$$ — массив из $$$n$$$ элементов, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз. Изначально каждый элемент перестановки покрашен в белый цвет.

Игроки ходят по очереди, первой ходит Алиса. На своём ходу игрок выбирает от $$$1$$$ до $$$k$$$ белых элементов и красит их либо в красный, либо в синий цвет. Все элементы, выбранные за один ход, должны получить один и тот же цвет.

Игра заканчивается, когда белых элементов не остаётся. Если получившуюся перестановку можно отсортировать в возрастающем порядке, меняя местами элементы одинаковых цветов, выигрывает Алиса. Иначе выигрывает Боб. Менять местами можно любые элементы при условии, что у них одинаковый цвет.

Определите, кто выиграет, если оба игрока играют оптимально.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le \min(20, n)$$$) — длину перестановки и максимальное количество элементов, которые можно покрасить за один ход;
  • вторая строка содержит $$$n$$$ целых попарно различных чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите в отдельной строке Alice, если выигрывает Алиса, или Bob, если выигрывает Боб.

Пример
Входные данные
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
Выходные данные
Alice
Bob
Alice
Bob
Alice
Alice
Bob
Bob
Alice
Bob