P12943 [NERC 2019] Just Arrange the Icons

BerPhone X 即将发布，手机预装了 $n$ 个应用程序。每个应用程序都有一个**类别**，用于描述该应用的类型或主题（如"游戏"、"商业"或"教育"）。类别用 $1$ 到 $n$ 之间的整数表示，第 $i$ 个应用程序的类别为 $c_i$。 你需要选择两个参数： - $m$ —— 屏幕数量 - $s$ —— 每个屏幕的容量 要求将所有 $n$ 个应用图标（每个图标代表一个应用）按照以下规则排列： 1. 同一屏幕上的所有图标必须属于同一类别的应用（不同屏幕可以包含同一类别的图标）； 2. 每个屏幕必须要么完全填满图标（图标数量等于 $s$），要么几乎填满（图标数量等于 $s-1$）。 你的任务是找出满足条件的最小屏幕数量 $m$。

第一行包含一个整数 $t$（$1 \le t \le 10\,000$）—— 测试用例的数量。随后是 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^6$）—— 图标数量。第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$），其中 $c_i$ 表示第 $i$ 个应用的类别。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^6$。

输出 $t$ 个整数 —— 按输入顺序给出每个测试用例的答案。每个答案是一个整数 $m$，表示满足条件所需的最小屏幕数量。

在第一个测试用例中，所有图标可以排列在 3 个容量为 4 的屏幕上： - 1 个屏幕放置 4 个类别 1 的图标 - 1 个屏幕放置 3 个类别 1 的图标 - 1 个屏幕放置 4 个类别 5 的图标 翻译由 DeepSeek V3 完成