Супер Жадібник 2

Двоє грають у гру "Супер Жаднюга". Є 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.

Приклади