Description

BerPhone X 即将发布，手机预装了 $n$ 个应用程序。每个应用程序都有一个类别，用于描述该应用的类型或主题（如"游戏"、"商业"或"教育"）。类别用 $1$ 到 $n$ 之间的整数表示，第 $i$ 个应用程序的类别为 $c_i$。

你需要选择两个参数：

• $m$ —— 屏幕数量
• $s$ —— 每个屏幕的容量

要求将所有 $n$ 个应用图标（每个图标代表一个应用）按照以下规则排列：

1. 同一屏幕上的所有图标必须属于同一类别的应用（不同屏幕可以包含同一类别的图标）；
2. 每个屏幕必须要么完全填满图标（图标数量等于 $s$），要么几乎填满（图标数量等于 $s-1$）。

你的任务是找出满足条件的最小屏幕数量 $m$。

Input Format

第一行包含一个整数 $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$。

Output Format

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

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

3
3
4

Hint

在第一个测试用例中，所有图标可以排列在 3 个容量为 4 的屏幕上：

• 1 个屏幕放置 4 个类别 1 的图标
• 1 个屏幕放置 3 个类别 1 的图标
• 1 个屏幕放置 4 个类别 5 的图标

翻译由 DeepSeek V3 完成