CF1267J.Just Arrange the Icons

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$，即满足要求的最小屏幕数量。

在示例的第一个测试用例中，所有图标可以放在三个容量为 $4$ 的屏幕上：一个放 $4$ 个类别为 $1$ 的图标，一个放 $3$ 个类别为 $1$ 的图标，一个放 $4$ 个类别为 $5$ 的图标。

由 ChatGPT 4.1 翻译