Двое играют в игру "Жадина". Есть \textbf{n} кучек из \textbf{a_i} конфет. Из любой кучи двое по-очереди тянут любое количество конфет от \textbf{1} до \textbf{k}. Проигрывает тот, кто берёт последнюю конфету в какой-либо кучке. Сколько способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих. \InputFile В первой строке записано количество партий \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10^5}). В следующих \textbf{t} строках записано описание партий: \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}), \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^9}) и \textbf{n} чисел \textbf{a_i} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{10^9}). Гарантируется, что суммарное количество кучек во всех партиях не превосходит \textbf{10^5}. \OutputFile Для каждой партии выведите количество способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих. Если первый игрок проигрывает выведите \textbf{0}.