← 返回题目列表

Codeforces · 1790/D

D. 俄罗斯套娃

中文机器翻译题面 查看原题

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 代表一个单独的集合。