Matryoshka 是一种彩绘娃娃形式的木制玩具,里面可以放一个较小尺寸的类似娃娃。
一套嵌套娃娃包含一个或多个嵌套娃娃,它们的大小为连续的正整数。因此,一组嵌套娃娃由两个数字描述:$$$s$$$ — 一组中最小嵌套娃娃的大小,$$$m$$$ — 一组中娃娃的数量。换句话说,对于某个整数 $$$s$$$ 和 $$$m$$$ ($$$s,m > 0$$$),该集合包含 $$$s、s + 1、\dots、s + m - 1$$$ 的大小。
您有一套或多套嵌套娃娃。最近,您发现有人将您的所有套装混合在一起,并记录了一系列娃娃尺寸 - 整数 $$$a_1、a_2、\dots、a_n$$$。
您不记得自己拥有多少组,因此您想要找到最初可以拥有的最小组数。
例如,如果给定序列为 $$$a=[2, 2, 3, 4, 3, 1]$$$。最初,可能有 $$$2$$$ 组:
- 第一组由 $$$4$$$ 嵌套娃娃组成,尺寸为 $$$[1, 2, 3, 4]$$$;
- 第二套由 $$$2$$$ 嵌套娃娃组成,尺寸为 $$$[2, 3]$$$。
根据给定的嵌套娃娃 $$$a_1, a_2, \dots, a_n$$$ 的尺寸序列,确定可以组成该序列的最小嵌套娃娃数量。
每套都已完全使用,因此其所有嵌套娃娃均已使用。给定序列的每个元素必须恰好对应于某个集合中的一个玩偶。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 所有集合中的俄罗斯套娃总数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 俄罗斯套娃的大小。
保证所有测试用例的$$$n$$$值之和不超过$$$2\cdot10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$k$$$ — 俄罗斯套娃组的最小可能数量。
示例
输入 #1
10 6 2 2 3 4 3 1 5 11 8 7 10 9 6 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 8 1 1 4 4 2 3 2 3 6 1 2 3 2 3 4 7 10 11 11 12 12 13 13 7 8 8 9 9 10 10 11 8 4 14 5 15 6 16 7 17 8 5 15 6 14 8 12 9 11 5 4 2 2 3 4
输出 #1
2 1 6 2 2 2 2 2 4 3
注意
第一个测试用例在问题陈述中进行了描述。
在第二个测试用例中,所有俄罗斯套娃都可以是同一组的一部分,最小尺寸为 $$$s=7$$$。
在第三个测试用例中,每个 matryoshka 代表一个单独的集合。