题目描述

你有一个整数数组 $a_1\dots a_N$，其元素初始值在范围 $[1,N]$ 内（$1\le N\le 2\cdot 10^5$），以及一个非零整数 $K$（$-N \le K\le N, K\neq 0$）。

你可以执行任意多次（包括零次）以下操作：选择一个下标 $i$ 并令 $a_i=a_i+K$。

求使得所有数组元素互不相同的最少操作次数。

输入格式

输入包含 $T$（$1\le T\le 10$）组独立的测试数据。每组测试数据的描述如下：

第一行包含 $N$ 和 $K$。

第二行包含 $a_1\dots a_N$。

保证所有测试数据的 $N$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含最少操作次数。

注意：本题涉及的整数较大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。

样例

输入 1

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

输出 1

2
4
2
1

说明 1

对于第一组测试数据，以下是一种使得所有元素互不相同的操作序列：

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

子任务

• 测试点 2-4：$N\le 50$
• 测试点 5-7：$N\le 2000$
• 测试点 8-10：$K=1$
• 测试点 11-13：无额外限制。

题目来源：Akshaj Arora, Benjamin Qi