Магічна множина

Задано послідовність цілих чисел a[1], a[2], ..., a[n] і ціле число m.

Назвемо хорошою послідовністю таку непорожню послідовність цілих чисел, для якої сума елементів будь-якої її непорожньої підпослідовності ділиться на m.

Знайдіть кількість хороших підпослідовностей у заданій послідовності a.

Вхідні дані

Перша стрічка містить кількість тестів t. Перша стрічка кожного тесту містить два цілі числа n (1 ≤ n ≤ 30) і m (1 ≤ m ≤ 1000). Друга стрічка містить n цілих чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 1000).

Вихідні дані

Для кожного тесту виведіть в окремому рядку одне число - кількість знайдених хороших підпослідовностей.

Приклади