Вам дан массив целых чисел \(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\).
Выходные данные
Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы произведение всех чисел массива делилось на \(k\).
Примечание
В первом наборе входных данных нужно два раза выбрать индекс \(i = 2\). После этого массив будет равен \(a = [7, 5]\). Произведение всех чисел массива равно \(35\).
В четвертом наборе входных данных произведение чисел массива равно \(120\), что уже делится на \(5\), поэтому не нужно применять операции.
В восьмом наборе входных данных можно сделать две операции, выбрав \(i = 2\) и \(i = 3\) в любом порядке. После этого массив будет равен \(a = [1, 6, 10]\). Произведение чисел массива равно \(60\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|