B. M-массивы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, a_2, \ldots, a_n$$$, состоящий из $$$n$$$ положительных целых чисел, и положительное целое число $$$m$$$.

Вы должны разделить элементы этого массива на несколько массивов. Внутри каждого из массивов вы можете переставить числа как угодно.

Назовём массив $$$m$$$-делимым, если сумма любых двух соседних чисел массива делится на $$$m$$$ (соседними называются числа, стоящие на позициях $$$i$$$ и $$$i+1$$$ для некоторого $$$i$$$). Массив из одного элемента является $$$m$$$-делимым.

Найдите наименьшее количество $$$m$$$-делимых массивов, на которые можно разделить $$$a_1, a_2, \ldots, a_n$$$.

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

В первой строке находится единственное целое число $$$t$$$ $$$(1 \le t \le 1000)$$$  — количество наборов входных данных.

В первой строке описания каждого набора входных данных находится два целых числа $$$n$$$, $$$m$$$ $$$(1 \le n \le 10^5, 1 \le m \le 10^5)$$$.

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$10^5$$$.

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

Для каждого набора входных данных выведите ответ на задачу.

Пример
Входные данные
4
6 4
2 2 8 6 9 4
10 8
1 1 1 5 2 4 4 8 6 7
1 1
666
2 2
2 4
Выходные данные
3
6
1
1
Примечание

В первом наборе входных данных можно разделить массив следующим образом:

  • $$$[4, 8]$$$. Этот массив является $$$4$$$-делимым, потому что $$$4+8$$$ делится на $$$4$$$.
  • $$$[2, 6, 2]$$$. Этот массив является $$$4$$$-делимым, потому что $$$2+6$$$ и $$$6+2$$$ делятся на $$$4$$$.
  • $$$[9]$$$. Этот массив является $$$4$$$-делимым, потому что он состоит из одного элемента.