Make All Distinct

You have an integer array $a_1\dots a_N$ with elements initially in the range $[1,N]$ ($1\le N\le 2\cdot 10^5$), as well as a nonzero integer $K$ ($-N \le K\le N, K\neq 0$).

You may perform the following operation as many times as you'd like (possibly zero): select an index $i$ and set $a_i=a_i+K$.

Find the minimum number of operations to make all array elements distinct.

The input consists of $T$ ($1\le T\le 10$) independent tests. Each test is described as follows:

The first line contains $N$ and $K$.

The second line contains $a_1\dots a_N$.

It is guaranteed that the sum of $N$ over all tests does not exceed $10^6$.

• Inputs 2-4: $N\le 50$
• Inputs 5-7: $N\le 2000$
• Inputs 8-10: $K=1$
• Inputs 11-13: No additional constraints.

For each test, output a single line containing the minimum number of operations.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

For the first test, here is a possible sequence of two operations that makes all elements distinct.