Задана последовательность целых чисел a1, a2, ..., an и целое число m.

Определим хорошей последовательностью целых чисел такую непустую последовательность, что сумма элементов ее любой непустой подпоследовательности делится на m.

Найдите количество хороших подпоследовательностей для заданной последовательности a.

Входные данные

Первая строка содержит количество тестов t. Первая строка каждого теста содержит два целых числа n (1 ≤ n ≤ 30) и m (1 ≤ m ≤ 1000). Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000).

Выходные данные

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