Супер Жадюга

Двоє гравців змагаються у грі "Жаднюга". На столі є n купок, кожна з яких містить a_i цукерок. Гравці по черзі беруть з будь-якої купки від 1 до k цукерок. Той, хто бере останню цукерку з купки, програє. Потрібно визначити, скільки є способів для першого гравця зробити виграшний перший хід, якщо обидва грають оптимально.

Вхідні дані

Перший рядок містить кількість партій t (1 ≤ t ≤ 10^5). Кожна з наступних t рядків описує одну партію: n (1 ≤ n ≤ 10^5), k (1 ≤ k ≤ 10^9) та n чисел a_i (1 ≤ a_i ≤ 10^9).

Гарантується, що загальна кількість купок у всіх партіях не перевищує 10^5.

Вихідні дані

Для кожної партії виведіть кількість способів, якими перший гравець може зробити виграшний перший хід, якщо обидва грають оптимально. Якщо перший гравець не може виграти, виведіть 0.

Приклади