Tất Cả Phân Biệt

Cho một mảng số nguyên gồm $N$ phần tử, mỗi phần tử có giá trị trong đoạn $[1,N]$, và một số nguyên $K$ khác $0$ ($-N\le K\le N$).

Bạn có thể thực hiện phép biến đổi: chọn một chỉ số $i$ và gán $a_i=a_i+K$.

Tìm số phép biến đổi ít nhất để tất cả các phần tử trong mảng đôi một khác nhau.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le 10$)
• Với mỗi bộ test:
  • Dòng 1: Hai số nguyên $N$ và $K$
  • Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$

Tổng $N$ trên tất cả các bộ test không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — số phép biến đổi ít nhất cần thực hiện.

Ràng buộc

• $1\le N\le 2\times {10}^5$
• $-N\le K\le N$, $K\ne 0$
• $1\le a_i\le N$
• Kết quả có thể lớn, cần sử dụng kiểu số nguyên 64-bit

Ví dụ

Ghi chú

• Test 2-4: $N\le 50$
• Test 5-7: $N\le 2000$
• Test 8-10: $K=1$
• Test 11-13: Không có ràng buộc bổ sung