Description

【部分不宜展示的内容已被删除】

「我们必须立刻改变！从现在起，花果山所有桃树结下的桃子，直接接收后，再重新分配给花果山上的猴子，直到所有猴子都拥有等量的桃子为止！」

孙悟空要求统计所有猴子所拥有的桃子以及桃树每天的桃子产量。花果山统计局很快地将相关数据呈给孙悟空：花果山上总共有 $n$ 只猴子，第 $i$ 只猴子拥有 $a_i$ 颗桃子，而桃树的产量很稳定，每天都能够生产出 $k$ 颗桃子。

花果山的内政大臣天命人针对重新分配的方法，向孙悟空提出建言：「为了花果山上的和谐，重新分配桃子时，不可以从猴子手中夺走任何桃子。每天接收到的桃子，必须当天就分配出去。最重要的是要避免相对剥夺感，每一天分配到最多桃子的猴子，只能比分配到最少桃子的猴子多得一颗桃子。」孙悟空觉得很有道理，便要求按照天命人的建议进行分配。

假设 $n=4,k=7,a_1=1,a_2=2,a_3=3,a_4=4$，即花果山上总共有 4 只猴子，分别有 1, 2, 3, 4 颗桃子，而桃树每天的产量是 7 颗桃子。按照天命人的建议，每只猴子每天都可以分配到一颗或是两颗桃子，不能更少也不能更多，否则会带来相对剥夺感。此时可以通过下列步骤，让所有的猴子拥有等量的桃子：

1. 第一天到第三天都分配各两颗桃子给前三只猴子、一颗桃子给第四只猴子。三天过后，四只猴子分别拥有 7, 8, 9, 7 颗桃子。
2. 第四天、第五天都分配各两颗桃子给前两只猴子、一颗桃子给第三只猴子、两颗桃子给第四只猴子。五天过后，四只猴子分别拥有 11, 12, 11, 11 颗桃子。
3. 第六天分配一颗桃子给第二只猴子、各两颗桃子给其余的三只猴子。六天过后，四只猴子分别拥有 13, 13, 13, 13 颗桃子，数量相等。

请撰写一个程序计算，最少要几天之后，才能使得所有的猴子都拥有等量的桃子。

Input Format

$$\begin{aligned} &T \\ &\text{testcase}_1 \\ &\text{testcase}_2 \\ &\vdots \\ &\text{testcase}_T \end{aligned}$$

• $T$ 表示测试数据个数。
• $\text{testcase}_i$ 为第 $i$ 笔测试资料。

每一笔测试资料的输入格式如下

$$\begin{aligned} &n \ k \\ &a_1 \ a_2 \ \ldots \ a_n \end{aligned}$$

• $n$ 为猴子的数量。
• $k$ 为桃子每天的产量。
• $a_i$ 代表第 $i$ 只猴子拥有的桃子数量。

Output Format

输出 $T$ 笔测试资料之答案

$$\begin{aligned} &\text{answer}_1 \\ &\text{answer}_2 \\ &\vdots \\ &\text{answer}_T \end{aligned}$$

• $\text{answer}_i$ 为第 $i$ 笔测试资料之答案。

每一笔测试资料答案的输出格式如下：如该组测试资料在 $x$ 天后，所有猴子能够拥有等量的桃子，则输出一个整数 $x$，如果那天永远不可能到来，则输出 poor monkeys。

5
4 7
1 2 3 4
4 4
1 2 3 4
8 3
1 1 2 3 4 5 6 9
8 4
1 1 2 3 4 5 6 9
2 1
0 1

6
poor monkeys
19
poor monkeys
1

Hint

数据限制

• $1 \leq T \leq 5 \times 10^5$。
• $2 \leq n \leq 10^6$。
• $1 \leq k \leq 10^9$。
• $0 \leq a_i \leq 10^9$。
• $a_1 \leq a_2 \leq \dots \leq a_n$ 且 $a_1 < a_n$。
• 输入的数皆为整数。
• $T$ 笔测试资料中 $n$ 的总和 $\sum n \leq 10^6$。

评分说明

本题共有五组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	2	$\sum n \leq 100$，$k = 1$，$a_i \leq 100$ 且保证最少天数存在。
2	3	$\sum n \leq 100$，$k = n-1$，$a_i \leq 100$ 且保证最少天数存在。
3	29	$\sum n \leq 1000$，$k \leq 1000$，$a_i \leq 1000$ 且保证若最少天数存在，则不超过 $10^4$。
4	39	$\sum n \leq 10^5$，$k \leq 10^5$，$a_i \leq 10^5$，见注 2。
5	27	无额外限制。

• 注 1：「最少天数存在」的意思是有一天所有猴子可以拥有等量的桃子，不存在的意思则是这一天永远不可能到来。
• 注 2：子任务 4 保证对于那些最少天数存在的测试资料，最少天数的总和不超过 $10^5$。换句话说，正确答案中输出的数字总和不超过 $10^5$。