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 \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$，表示满足给定要求的情况下，放置所有 $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$ 的屏幕上：一个屏幕放置 $4$ 个类别为 $1$ 的图标，一个屏幕放置 $3$ 个类别为 $1$ 的图标，以及一个屏幕放置 $4$ 个类别为 $5$ 的图标。