You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

又是 Farmer John 的农场上寒冷而无聊的一天。为了打发时间，Farmer John 发明了一种关于在整数数组上进行操作的有趣的休闲活动。

Farmer John 有一个包含 $N$（$1 \leq N \leq 2 \cdot 10^5$）个非负整数的数组 $a$ 和一个整数 $M$（$1 \leq M \leq 10^9$）。然后，FJ 会请 Bessie 给出一个整数 $x$。在一次操作中，FJ 可以选择一个索引 $i$，并对 $a_i$ 加 $1$ 或减 $1$。FJ 的无聊值是他必须执行的最小操作次数，以使得对于所有的 $1 \leq i \leq N$，$a_i-x$ 均可被 $M$ 整除。

对于所有可能的 $x$，输出 FJ 的最小无聊值。

输入格式

输入的第一行包含 $T$（$1 \leq T \leq 10$），为需要求解的独立的测试用例数量。

每一个测试用例的第一行包含 $N$ 和 $M$。

第二行包含 $a_1, a_2, ..., a_N$ （$0 \leq a_i \leq 10^9$）。

输入保证所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每一个测试用例输出一行，包含对于所有可能的 $x$，FJ 的最小无聊值。

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

10
21

提示

样例解释

在第一个测试用例中，$x$ 的一个最优选择是 $3$。FJ 可以执行 $10$ 次操作使得 $a = [12, 12, 21, 3, 12]$。

子任务

• 测试点 2：$N \le 1000$ 以及 $M \le 1000$。
• 测试点 3：$N\le 1000$。
• 测试点 4-5：$M\le 10^5$。
• 测试点 6-16：没有额外限制。