Lại là một ngày lạnh lẽo và buồn chán tại trang trại của Farmer John. Để giết thời gian, Farmer John đã nghĩ ra một hoạt động giải trí thú vị liên quan đến việc thực hiện các thao tác trên một mảng số nguyên.

Farmer John có một mảng \(a\) gồm \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) số nguyên không âm và một số nguyên \(M\) (\(1 \leq M \leq 10^9\)). Sau đó, FJ sẽ hỏi Bessie một số nguyên \(x\). Trong một thao tác, FJ có thể chọn một chỉ số \(i\) rồi trừ \(1\) khỏi hoặc cộng \(1\) vào \(a_i\). Giá trị buồn chán của FJ là số thao tác ít nhất ông phải thực hiện sao cho \(a_i-x\) chia hết cho \(M\) với mọi \(1 \leq i \leq N\).

Trong tất cả các giá trị \(x\) có thể, hãy in giá trị buồn chán nhỏ nhất có thể của FJ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 10\)), số bộ test độc lập cần giải.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(M\).

Dòng thứ hai của mỗi bộ test chứa \(a_1, a_2, ..., a_N\) (\(0 \leq a_i \leq 10^9\)).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5 \cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng một số nguyên là giá trị buồn chán nhỏ nhất có thể của FJ trong tất cả các giá trị \(x\) có thể.

Ví dụ

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853

10
21

Phân nhóm

• Input 2: \(N \le 1000\) và \(M \le 1000\).
• Input 3: \(N\le 1000\).
• Inputs 4-5: \(M\le 10^5\).
• Inputs 6-16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Farmer John's Favorite Operation

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1471

Tác giả đề: Chongtian Ma