Mảng dư không

Cho một mảng $a$ gồm $n$ số nguyên dương.

Ban đầu bạn có một số nguyên $x=0$. Trong mỗi bước, bạn được chọn thực hiện đúng một trong hai thao tác sau:

1. Chọn đúng một chỉ số $i$ (từ $1$ đến $n$), tăng $a_i$ thêm $x$ (tức $a_i:=a_i+x$), rồi tăng $x$ thêm $1$ (tức $x:=x+1$).
2. Chỉ tăng $x$ thêm $1$ (tức $x:=x+1$).

Thao tác loại 1 chỉ được áp dụng nhiều nhất một lần cho mỗi chỉ số $i$.

Hãy tìm số bước ít nhất cần thực hiện để thu được mảng mà mọi phần tử đều chia hết cho $k$.

Bạn phải trả lời $t$ truy vấn độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $k$ — độ dài mảng và ước số cần thoả.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên là số bước ít nhất cần thực hiện để mọi phần tử của mảng đều chia hết cho $k$.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $1\le n\le 2·{10}^5$
• $1\le k\le {10}^9$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các truy vấn không vượt quá $2·{10}^5$.

Ví dụ