C. Малинки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и число $$$k$$$ ($$$2 \leq k \leq 5$$$). За одну операцию вы можете сделать следующее:

  • Выбрать индекс $$$1 \leq i \leq n$$$,
  • Сделать $$$a_i = a_i + 1$$$.

Найдите наименьшее количество операций, которые нужно сделать, чтобы произведение всех чисел массива $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$ делилось на $$$k$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 5$$$) — размер массива $$$a$$$ и число $$$k$$$.

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

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

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

Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы произведение всех чисел массива делилось на $$$k$$$.

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

В первом наборе входных данных нужно два раза выбрать индекс $$$i = 2$$$. После этого массив будет равен $$$a = [7, 5]$$$. Произведение всех чисел массива равно $$$35$$$.

В четвертом наборе входных данных произведение чисел массива равно $$$120$$$, что уже делится на $$$5$$$, поэтому не нужно применять операции.

В восьмом наборе входных данных можно сделать две операции, выбрав $$$i = 2$$$ и $$$i = 3$$$ в любом порядке. После этого массив будет равен $$$a = [1, 6, 10]$$$. Произведение чисел массива равно $$$60$$$.