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⋅105) non-negative integers and an integer M (1≤M≤109). Then, FJ will ask Bessie for an integer x. In one operation, FJ can pick an index i and subtract or add 1 to ai. FJ's boredom value is the minimum number of operations he must perform so that ai−x is divisible by M for all 1≤i≤N.
Among all possible x, output FJ's minimum possible boredom value.
In the first test case, one optimal choice of x is 3. FJ can perform 10 operations to make a=[12,12,21,3,12].
SCORING:
- Input 2: N≤1000 and M≤1000.
- Input 3: N≤1000.
- Inputs 4-5: M≤105.
- Inputs 6-16: No additional constraints.
Problem credits: Chongtian Ma
Source: USA Computing Olympiad.
Input Format
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 a1,a2,...,aN (0≤ai≤109).
It is guaranteed that the sum of N over all test cases does not exceed 5⋅105.
Output Format
For each test case, output an integer on a new line containing FJ's minimum possible boredom value among all possible values of x.