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

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

Задан массив целых чисел $$$a_1, a_2, \dots, a_n$$$, все его элементы различны.

Сначала вы вставляете в этот массив еще одно целое число $$$a_{n+1}$$$. $$$a_{n+1}$$$ не должно быть равно ни одному из $$$a_1, a_2, \dots, a_n$$$.

Затем все элементы массива надо будет сделать равными. Для этого вы выбираете положительное целое число $$$x$$$ ($$$x > 0$$$). После этого за одну операцию вы прибавляете $$$x$$$ ровно к одному элементу массива. Обратите внимание, что $$$x$$$ одинаковый для всех операций.

Какое наименьшее количество операций вам потребуется, чтобы сделать все элементы равными, после выбора $$$a_{n+1}$$$ и $$$x$$$?

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

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

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). Все $$$a_i$$$ различны.

Сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — наименьшее количество операций, которое вам потребуется, чтобы сделать все элементы равными, после выбора целых чисел $$$a_{n+1}$$$ и $$$x$$$.

Пример
Входные данные
3
3
1 2 3
5
1 -19 17 -3 -15
1
10
Выходные данные
6
27
1
Примечание

В первом наборе входных данных вы можете выбрать $$$a_{n+1} = 4$$$, массив станет $$$[1, 2, 3, 4]$$$. Затем вы можете выбрать $$$x = 1$$$ и применить операцию $$$3$$$ раза к первому элементу, $$$2$$$ раза ко второму элементу, $$$1$$$ раз к третьему элементу и $$$0$$$ раз к четвертому элементу.

Во втором наборе вы можете выбрать $$$a_{n+1} = 13, x = 4$$$.

В третьем наборе вы можете выбрать $$$a_{n+1} = 9, x = 1$$$. Затем применить операцию один раз к $$$a_{n+1}$$$.