Alice 正在邀请她的朋友参加聚会吃蛋糕。然而,每个朋友可能不在同一个地方,所以大家必须先在同一个地点见面。
Alice 有 $$$n$$$ 个朋友,其中第 $$$i$$$ 位朋友位于 $$$a_i$$$ 位置。为了让每个人都在同一个地方,Alice 必须进行多次群组通话。不幸的是,信号很弱,Alice 一次只能呼叫 $$$2$$$ 其他人。
作为一个好人,爱丽丝不希望她的朋友走得太远。因此,对于包含第 $$$i$$$ 个朋友和第 $$$j$$$ 个朋友的每个群组通话,Alice 会告诉他们两个在 $$$\min(a_i, a_j)$$$ 和 $$$\max(a_i, a_j)$$$(含)之间的某个整数位置见面。之后,他们两人都会快速移动到该位置,以至于Alice在移动过程中无法进行任何群组通话。请注意,一旦这些朋友到达该位置,爱丽丝就可以再次呼叫他们。
聚会即将开始,因此 Alice 需要快速进行群组通话。帮助她找到需要拨打的最少群组通话次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — Alice 的朋友数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 她朋友的位置。
输出
对于每个测试用例,输出她需要进行的最少群组通话次数,以便她的所有朋友都在同一位置。
示例
输入复制
451 2 3 4 551 1 1 2 2113 1 4 1 5 9 2 6 5 3 551 2 2 2 2
输出复制
2251
注意
在第一个测试用例中,组呼的最小数量为 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]$$$。