← 返回题目列表

Codeforces · 1267/J

J. 只需排列图标即可

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

BerPhone X 即将发布,手机上预装了 $$$n$$$ 应用程序。应用程序的类别表征了该应用程序的流派或主题(例如“游戏”、“商业”或“教育”)。类别以 $$$1$$$ 和 $$$n$$$(含)之间的整数给出;第 $$$i$$$ 个应用程序的类别为 $$$c_i$$$。

您可以选择 $$$m$$$ — 屏幕数量和 $$$s$$$ — 每个屏幕的大小。您需要安装应用程序的所有 $$$n$$$ 图标(一个图标代表一个应用程序),并满足以下要求:

- 每个屏幕上,所有图标必须属于同一类别的应用程序(但不同屏幕可以包含同一类别应用程序的图标);
- 每个屏幕必须完全充满图标(屏幕上的图标数量等于 $$$s$$$)或几乎充满图标(图标数量等于 $$$s-1$$$)。

你的任务是找到尽可能少的屏幕数量$$$m$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^6$$$) — 图标的数量。第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个应用程序的类别。

保证输入中所有测试用例的$$$n$$$值的总和不超过$$$2\cdot10^6$$$。

输出

打印 $$$t$$$ 整数 — 按照输入中的顺序给出给定测试用例的答案。测试用例的答案是一个整数$$$m$$$——可以放置满足给定要求的所有$$$n$$$图标的最小屏幕数量。

示例

输入 #1

3
11
1 5 1 5 1 5 1 1 1 1 5
6
1 2 2 2 2 1
5
4 3 3 1 2

输出 #1

3
3
4

注意

在示例的第一个测试用例中,所有图标都可以放置在三个大小为 $$$4$$$ 的屏幕上:一个具有 $$$1$$$ 类别的 $$$4$$$ 图标的屏幕,一个具有 $$$1$$$ 类别的 $$$3$$$ 图标的屏幕,以及一个具有 $$$5$$$ 类别 $$$4$$$ 图标的屏幕。