题目描述

某地区正在进行 “大胃王” 活动，共有 $n$ 名选手参与活动，第 $i$ 名选手初始时有 $a_i$ 份食物，所有选手的食物均不相同。

活动分为若干轮。每一轮，所有选手都会吃掉 $x$ 份食物，如果某位选手的剩余食物不够 $x$ 份，那么该选手会吃掉所有剩下的食物。这里面的 $x$ 是指在上一轮结束后这一轮开始前，所有参赛选手的食物份数的种类数。例如，某一轮开始前， $5$ 位选手的剩余食物份数为 $\{2,2,3,5,6\}$，那么这一轮所有人都会吃掉 $4$ 份食物（不同的数字数量为 $4$），这一轮后五名选手的剩余食物份数为 $\{0,0,0,1,2\}$。

现在，请你求出，至少要进行多少轮活动，才能使得所有选手的剩余食物份数相等。

输入格式

输入包含多组数据。第一行一个正整数 $T$，表示数据组数，对于每组数据：

第一行一个正整数 $n$ 表示选手数量。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每位选手的初始食物份数。

输出格式

对于每组数据，输出一个整数，代表要使得所有选手的剩余食物份数相等的最少轮数。

2
5
10 0 9 1 10
5
1 3 6 10 16

3
5

1
2
2 2

0

样例解释

在第一组样例中，活动过程如下：

第一轮，种类数 $x=4$，这一轮过后选手的剩余食物份数为 $\{6,0,5,0,6\}$；

第二轮，种类数 $x=3$，这一轮过后选手的剩余食物份数为 $\{3,0,2,0,3\}$；

第三轮，种类数 $x=3$，这一轮过后选手的剩余食物份数为 $\{0,0,0,0,0\}$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^2,1 \leq n,\sum n \leq 2 \times 10^{5},0 \leq a_i \leq 10^{18}$。