题目描述

Alice 要邀请朋友们来吃蛋糕。朋友们一开始可能在不同的位置，因此大家需要先汇合到同一个位置。

Alice 有 $n$ 个朋友，第 $i$ 个朋友在位置 $a_i$。为了让所有人到达同一个位置，Alice 可以进行多次群组通话。由于信号不好，每次她只能同时呼叫恰好两个朋友。

对于一次包含第 $i$ 个和第 $j$ 个朋友的通话，Alice 可以让他们二人移动到任意一个整数位置 $x$，满足 $\min(a_i,a_j) \le x \le \max(a_i,a_j)$。他们会立刻移动过去，移动过程中 Alice 不能进行其他通话；到达后可以再次被呼叫。

请你求出最少需要多少次通话，才能让所有朋友处在同一个位置。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据第一行包含一个整数 $n$，表示朋友数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个朋友的位置。

输出格式

对于每组测试数据，输出一个整数，表示最少通话次数。

数据范围

• $1 \le t \le 500$
• $2 \le n \le 100$
• $1 \le a_i \le 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]$ 。

来源

Codeforces Round 2232 A - Convergence