描述

给定一个长度为 N 的整数数组 a，初始时每个元素都在 [1, N] 范围内；以及一个非零整数 K（-N ≤ K ≤ N，K ≠ 0）。你可以执行任意次操作：选择下标 i，将 a_i 替换为 a_i + K。目标是使数组中所有元素互不相同。求达成目标所需的最少操作次数。

输入输出格式

输入

第一行一个整数 T（1 ≤ T ≤ 10），表示测试用例数量。 对每个测试用例：

• 第一行包含两个整数 N 和 K；
• 第二行包含 N 个整数 a_1, a_2, ..., a_N。 保证所有测试用例的 N 总和不超过 10^6。

输出

对每个测试用例，输出一行一个整数，表示使所有元素互不相同的最少操作次数。

样例

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

2
4
2
1

限制

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 2×10^5
• 所有测试用例的 N 总和 ≤ 10^6
• -N ≤ K ≤ N，且 K ≠ 0
• 初始 a_i ∈ [1, N]