题目描述

又是 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：没有额外限制。