Вам задан массив \(a\), состоящий из \(n\) положительных целых чисел.
Изначально у вас есть целое число \(x = 0\). За один ход вы можете совершить одну из следующих двух операций:
- Выбрать ровно один индекс \(i\) от \(1\) до \(n\) и увеличить \(a_i\) на \(x\) (\(a_i := a_i + x\)), затем увеличить \(x\) на \(1\) (\(x := x + 1\)).
- Просто увеличить \(x\) на \(1\) (\(x := x + 1\)).
Первая операция может быть применена не более одного раза для каждого \(i\) от \(1\) до \(n\).
Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить такой массив, что каждый его элемент без остатка делится на \(k\) (значение \(k\) задано).
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него — минимальное количество ходов, необходимое, чтобы получить такой массив, что каждый его элемент без остатка делится на \(k\).
Примечание
Рассмотрим первый набор тестовых данных примера:
- \(x=0\), \(a = [1, 2, 1, 3]\). Надо просто увеличить \(x\);
- \(x=1\), \(a = [1, 2, 1, 3]\). Надо добавить \(x\) ко второму элементу и увеличить \(x\);
- \(x=2\), \(a = [1, 3, 1, 3]\). Надо добавить \(x\) к третьему элементу и увеличить \(x\);
- \(x=3\), \(a = [1, 3, 3, 3]\). Надо добавить \(x\) к четвертому элементу и увеличить \(x\);
- \(x=4\), \(a = [1, 3, 3, 6]\). Надо просто увеличить \(x\);
- \(x=5\), \(a = [1, 3, 3, 6]\). Надо добавить \(x\) к первому элементу и увеличить \(x\);
- \(x=6\), \(a = [6, 3, 3, 6]\). Мы получили необходимый массив.
Заметьте, что вы не можете добавить \(x\) к одному и тому же элементу больше, чем один раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8
|
6
18
0
227
8
|