Нео-Нім#13019

Нео-Нім

2 секунди
512 мегабайтів
Дуже складна

Є купок каменів. Спочатку -та купка містить a_i каменів. Також задано ціле число .

Ана та Боб грають у гру, по черзі виконуючи ходи, причому Ана ходить першою. Правила ходів такі:

Гравець, який не може зробити хід, програє. Визначте переможця за умови, що обидва гравці грають оптимально.

Вхідні дані

У першому рядку задано ціле число — кількість тестових випадків.

У першому рядку кожного тестового випадку задано два цілі числа і — кількість купок та максимальна кількість каменів, яку Ана може забрати за один хід.

У другому рядку кожного тестового випадку задано цілих чисел a_i — кількість каменів у кожній купці.

1 \le n \le 10^5,

2 \le k \le 10^5,

1 \le a_i \le 10^5,

сума значень за всіма тестовими випадками не перевищує 3 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть Ana, якщо перемагає Ана, або Bob, якщо перемагає Боб.

Приклади

Приклад

Loading
Loading

Примітка

У першому прикладі n = 3, k = 2, a = (2, 5, 8).

Один із можливих перебігів гри:

  • Ана забирає два камені з третьої купки. Після цього стає рівним (2, 5, 6).

  • Боб забирає один камінь із першої купки. Після цього стає рівним (1, 5, 6).

  • Ана забирає два камені з другої купки. Після цього стає рівним (1, 3, 6).

  • Боб забирає один камінь із третьої купки. Після цього стає рівним (1, 3, 5).

  • Ана забирає два камені з третьої купки. Після цього стає рівним (1, 3, 3).

  • Боб забирає один камінь із третьої купки. Після цього стає рівним (1, 3, 2).

  • Ана забирає два камені з другої купки. Після цього стає рівним (1, 1, 2).

  • Боб забирає один камінь із третьої купки. Після цього стає рівним (1, 1, 1).

  • Тепер черга Ани, але вона не може зробити хід. Ана програє, а Боб перемагає.

У першому прикладі перемагає Боб.

У другому прикладі перемагає Боб.

У третьому прикладі перемагає Ана.