문제

민영이는 $1$ 이상 $N$ 이하의 정수로 이루어진 길이 $N$의 수열 $a_1, a_2, \cdots, a_N$과 $0$이 아닌 정수 $K$를 가지고 있다. ($1 \le N \le 2 \cdot 10^5$; $-N \le K \le N, K \neq 0$)

민영이는 수열의 모든 원소를 서로 다르게 만들고 싶어 한다. 이를 위해 다음과 같은 연산을 원하는 만큼 수행할 수 있다(연산을 수행하지 않아도 된다).

• 인덱스 $i$를 선택하여 $a_i$의 값을 $a_i + K$로 바꾼다.

수열의 모든 원소가 서로 다르게 되도록 하기 위해 필요한 최소 연산 횟수를 구하시오.

입력

입력은 $T$개의 독립적인 테스트 케이스로 구성된다. ($1 \le T \le 10$)

각 테스트 케이스의 첫째 줄에는 $N$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에는 $N$개의 정수 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대한 $N$의 합은 $1\,000\,000$을 넘지 않는다.

출력

각 테스트 케이스마다 수열의 모든 원소를 서로 다르게 만들기 위한 최소 연산 횟수를 한 줄에 하나씩 출력한다.

참고: 이 문제에서 다루는 정수의 크기가 매우 클 수 있으므로, C/C++의 long long과 같은 64비트 정수 자료형을 사용하는 것을 권장한다.

예제 입력 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

점수

• 테스트 케이스 2~4: $N \le 50$
• 테스트 케이스 5~7: $N \le 2000$
• 테스트 케이스 8~10: $K = 1$
• 테스트 케이스 11~13: 추가 제약 조건 없음.