2034: [USACO 2025 January Contest, Silver] Problem 2. Farmer John's Favorite Operation

It is another cold and boring day on Farmer John's farm. To pass the time, Farmer John has invented a fun leisure activity involving performing operations on an integer array.

Farmer John has an array a of N (1 ≤ N ≤ 2⋅10⁵) non-negative integers and an integer M (1 ≤ M ≤ 10⁹). Then, FJ will ask Bessie for an integer x. In one operation, FJ can pick an index i and subtract or add 1 to a_i. FJ's boredom value is the minimum number of operations he must perform so that a_i−x is divisible by M for all 1 ≤ i ≤ N.

Among all possible x, output FJ's minimum possible boredom value.

The first line contains T (1≤T≤10), the number of independent test cases to solve.

The first line of each test case contains N and M.

The second line of each test case contains a₁,a₂,...,a_N (0 ≤ a_i ≤ 10⁹).

It is guaranteed that the sum of N over all test cases does not exceed 5⋅10⁵.

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

10
21