Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

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

До применения операций вы можете перемешать элементы массива как угодно. За одну операцию вы можете сделать следующее:

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

Массив $$$b_1, b_2, \ldots, b_n$$$ является красивым, если $$$b_i = b_{n - i + 1}$$$ для всех $$$1 \leq i \leq n$$$.

Найдите наименьшее количество операций, за которое можно сделать массив красивым, или сообщите, что это невозможно.

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

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

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

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

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

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

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

Пример
Входные данные
11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5
Выходные данные
0
83966524
1
4
6
1
48
-1
0
14
0
Примечание

В первом наборе входных данных массив уже является красивым.

Во втором наборе входных данных можно не перемешивать массив до операций и $$$83966524$$$ раз сделать операцию с индексом $$$i = 1$$$.

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

В восьмом наборе входных данных не существует набора операций и способа перемешать элементы, чтобы сделать массив красивым.

В девятом наборе входных данных массив уже является красивым.