A. Сходимость
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса приглашает своих друзей на вечеринку поесть тортики. Однако друзья могут находиться в разных местах, поэтому сначала всем нужно встретиться в одной точке.

У Алисы есть $$$n$$$ друзей, и $$$i$$$-й друг находится на позиции $$$a_i$$$. Чтобы все оказались в одном месте, Алисе нужно сделать несколько групповых звонков. К сожалению, сигнал слабый, и Алиса может одновременно позвонить только $$$2$$$ другим людям.

Будучи хорошим человеком, Алиса не хочет, чтобы её друзья шли слишком далеко. Поэтому для каждого группового звонка, содержащего $$$i$$$-го и $$$j$$$-го друга, Алиса скажет им обоим встретиться в некоторой целочисленной точке между $$$\min(a_i, a_j)$$$ и $$$\max(a_i, a_j)$$$ включительно. После этого они оба моментально переместятся в эту точку, так что Алиса не сможет сделать ни одного звонка во время их перемещения. Обратите внимание, что Алиса может снова позвонить этим друзьям, как только они достигнут этой точки.

Вечеринка скоро начнётся, поэтому Алисе нужно быстро делать групповые звонки. Помогите ей найти минимальное количество групповых звонков, которое ей нужно сделать.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — количество друзей Алисы.

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

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

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

Пример
Входные данные
4
5
1 2 3 4 5
5
1 1 1 2 2
11
3 1 4 1 5 9 2 6 5 3 5
5
1 2 2 2 2
Выходные данные
2
2
5
1
Примечание

В первом наборе входных данных минимальное количество групповых звонков равно 2. Один из способов сделать так, чтобы все оказались в одной точке, выглядит следующим образом:

  • Позвонить $$$1$$$-му и $$$4$$$-му другу и сказать им переместиться в точку $$$3$$$. Их позиции теперь равны $$$[3, 2, 3, 3, 5]$$$.
  • Позвонить $$$2$$$-му и $$$5$$$-му другу и сказать им переместиться в точку $$$3$$$. Их позиции теперь равны $$$[3, 3, 3, 3, 3]$$$.

Во втором наборе входных данных минимальное количество групповых звонков равно 2. Один из способов сделать так, чтобы все оказались в одной точке, выглядит следующим образом:

  • Позвонить $$$1$$$-му и $$$4$$$-му другу и сказать им переместиться в точку $$$1$$$. Их позиции теперь равны $$$[1, 1, 1, 1, 2]$$$.
  • Позвонить $$$4$$$-му и $$$5$$$-му другу и сказать им переместиться в точку $$$1$$$. Их позиции теперь равны $$$[1, 1, 1, 1, 1]$$$.