You have an integer array a1…aN with elements initially in the range [1,N](1≤N≤2⋅105), as well as a nonzero integer K(−N≤K≤N,K≠0).
You may perform the following operation as many times as you'd like (possibly zero): select an index i and set ai=ai+K.
Find the minimum number of operations to make all array elements distinct.
INPUT FORMAT (input arrives from the terminal / stdin):
The input consists of T (1≤T≤10) independent tests. Each test is described as follows:
The first line contains N and K.
The second line contains a1…aN .
It is guaranteed that the sum of N over all tests does not exceed 106.
OUTPUT FORMAT (print output to the terminal / stdout):
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++).
SAMPLE INPUT:
4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2
SAMPLE OUTPUT:
2
4
2
1
For the first test, here is a possible sequence of two operations that makes all elements distinct.
4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)
SCORING:
Inputs 2-4: N≤50
Inputs 5-7: N≤2000
Inputs 8-10: K=1
Inputs 11-13: No additional constraints.
Problem credits: Akshaj Arora, Benjamin Qi