Двое играют в игру "Супер Жадина". Есть \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{5}), \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10}) и \textbf{n} чисел \textbf{a_i} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{10}). \OutputFile Для каждой партии выведите количество способов сделать первый ход у первого игрока, чтобы победить при правильной игре обоих. Если первый игрок проигрывает выведите \textbf{0}.