题目描述

Alice 邀请她的朋友们去参加派对吃蛋糕。然而，大家所在的位置可能并不相同，因此所有人必须先在同一个地点集合。

Alice 有 $n$ 个朋友，其中第 $i$ 个朋友位于位置 $a_i$。为了让所有人聚到一起，Alice 需要拨打多次群组电话。不幸的是，由于信号太弱，Alice 每次只能同时呼叫另外 $2$ 个人。

作为一个体贴的人，Alice 不希望她的朋友们走得太远。因此，在每一次包含第 $i$ 个朋友和第 $j$ 个朋友的群组电话中，Alice 会让他们两人在 $\min(a_i, a_j)$ 到 $\max(a_i, a_j)$ 之间（包含边界）的某个整数坐标位置碰面。随后，这两人会迅速移动到该位置，在他们移动期间，Alice 无法拨打其他群组电话。请注意，一旦他们到达了约定的位置，Alice 之后还可以再次呼叫他们。

派对马上就要开始了，Alice 必须尽快打完这些电话。请你帮她计算，为了让所有朋友最终都聚在同一个位置，她最少需要拨打多少次群组电话。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 100$）—— Alice 的朋友数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 朋友们初始所在的位置。

输出格式

对于每个测试用例，输出一行一个整数，表示让所有朋友到达同一个位置所需的最少群组电话次数。

样例输入 1

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

样例输出 1

2
2
5
1

说明

样例解释

• 在第一个测试用例中，最少需要 $2$ 次群组电话。一种让所有人到达同一位置的方法如下：
  1. 呼叫第 $1$ 个和第 $4$ 个朋友，让他们在位置 $3$ 碰面。朋友们的位置变为 $[3, 2, 3, 3, 5]$。
  2. 呼叫第 $2$ 个和第 $5$ 个朋友，让他们在位置 $3$ 碰面。朋友们的位置变为 $[3, 3, 3, 3, 3]$。
• 在第二个测试用例中，最少需要 $2$ 次群组电话。一种让所有人到达同一位置的方法如下：
  1. 呼叫第 $1$ 个和第 $4$ 个朋友，让他们在位置 $1$ 碰面。朋友们的位置变为 $[1, 1, 1, 1, 2]$。
  2. 呼叫第 $4$ 个和第 $5$ 个朋友，让他们在位置 $1$ 碰面。朋友们的位置变为 $[1, 1, 1, 1, 1]$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 500$。
• 对于每个测试用例，保证 $2 \le n \le 100$，$1 \le a_i \le 10^9$。
• 保证所有的输入数值均为整数。