Дан массив \(a_1, a_2, \ldots, a_n\), состоящий из \(n\) положительных целых чисел, и положительное целое число \(m\).
Вы должны разделить элементы этого массива на несколько массивов. Внутри каждого из массивов вы можете переставить числа как угодно.
Назовём массив \(m\)-делимым, если сумма любых двух соседних чисел массива делится на \(m\) (соседними называются числа, стоящие на позициях \(i\) и \(i+1\) для некоторого \(i\)). Массив из одного элемента является \(m\)-делимым.
Найдите наименьшее количество \(m\)-делимых массивов, на которые можно разделить \(a_1, a_2, \ldots, a_n\).
Выходные данные
Для каждого набора входных данных выведите ответ на задачу.
Примечание
В первом наборе входных данных можно разделить массив следующим образом:
- \([4, 8]\). Этот массив является \(4\)-делимым, потому что \(4+8\) делится на \(4\).
- \([2, 6, 2]\). Этот массив является \(4\)-делимым, потому что \(2+6\) и \(6+2\) делятся на \(4\).
- \([9]\). Этот массив является \(4\)-делимым, потому что он состоит из одного элемента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|