Двое играют в игру "Жадина". Есть 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.