Супер Жадюга#3715
Двоє гравців змагаються у грі "Жадюга". На столі є купок, кожна з яких містить a_i цукерок. Гравці по черзі беруть з будь-якої купки від до цукерок. Той, хто бере останню цукерку з купки, програє. Потрібно визначити, скільки є способів для першого гравця зробити виграшний перший хід, якщо обидва грають оптимально.
Перший рядок містить кількість партій (1 \le t \le 10^5). Кожна з наступних рядків описує одну партію: (1 \le n \le 10^5), (1 \le k \le 10^9) та чисел a_i (1 \le a_i \le 10^9).
Гарантується, що загальна кількість купок у всіх партіях не перевищує 10^5.
Для кожної партії виведіть кількість способів, якими перший гравець може зробити виграшний перший хід, якщо обидва грають оптимально. Якщо перший гравець не може виграти, виведіть .
Приклад 1