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