D. Разделить и плюс K
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
eliteLAQ - Desert Ruins
⠀

На доске написаны $$$n$$$ целых положительных чисел $$$a_1, a_2, \dots, a_n$$$. Вам также дано целое положительное число $$$k$$$. Вы можете выполнить следующую операцию несколько (возможно, $$$0$$$) раз:

  • выбрать на доске число $$$x$$$;
  • стереть одно вхождение $$$x$$$;
  • написать на доске два положительных целых числа $$$y$$$, $$$z$$$ таких, что $$$y+z = x+k$$$.

Можно ли сделать так, чтобы все числа на доске стали равны? Если да, то какое минимальное количество операций вам потребуется?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^{12}$$$) — количество целых чисел, изначально записанных на доске, и константу $$$k$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — изначальный набор чисел на доске.

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

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

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

Пример
Входные данные
9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906
Выходные данные
3
1
4
-1
-1
0
3119
28999960732
-1
Примечание

В первом наборе входных данных $$$k = 1$$$. Вы можете сделать все числа на доске равными $$$2$$$ с помощью следующих операций:

  • Стереть $$$x = 4$$$ и написать $$$(y, z) = (2, 3)$$$. Обратите внимание, что $$$y+z=x+k$$$. Теперь на доске написано мультимножество $$$\{3, 2, 3\}$$$.
  • Стереть $$$x = 3$$$ и написать $$$(y, z) = (2, 2)$$$. Заметьте, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{2, 2, 2, 3\}$$$.
  • Стереть $$$x = 3$$$ и написать $$$(y, z) = (2, 2)$$$. Заметьте, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{2, 2, 2, 2, 2\}$$$.

Это делает все числа равными за $$$3$$$ операции. Можно показать, что нельзя сделать все числа равными менее чем за $$$3$$$ операции.

Во втором наборе входных данных $$$k = 3$$$. Вы можете сделать все числа на доске равными $$$7$$$ с помощью следующей операции:

  • Стереть $$$x = 11$$$ и написать $$$(y, z) = (7, 7)$$$. Обратите внимание, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{7, 7, 7\}$$$.

В третьем наборе входных данных $$$k = 10$$$. Вы можете сделать все числа на доске равными $$$40$$$ с помощью следующих операций:

  • Стереть $$$x = 100$$$ и написать $$$(y, z) = (70, 40)$$$. Обратите внимание, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{70, 40, 40, 100\}$$$.
  • Стереть $$$x = 70$$$ и написать $$$(y, z) = (40, 40)$$$. Обратите внимание, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{40, 40, 40, 40, 100\}$$$.
  • Стереть $$$x = 100$$$ и написать $$$(y, z) = (40, 70)$$$. Заметьте, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{40, 40, 40, 40, 40, 70\}$$$.
  • Стереть $$$x = 70$$$ и написать $$$(y, z) = (40, 40)$$$. Заметьте, что $$$y+z=x+k$$$. Теперь на доске написано $$$\{40, 40, 40, 40, 40, 40, 40\}$$$.

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