1986E - Beautiful Array - CodeForces Solution

def s():
  n,k = [int(i)for i in input().split()]
  a = [int(i)for i in input().split()];d={}
  for i in a:
    p = i%k
    if p not in d:d[p] = [i]
    else:d[p] += [i]
  v,ans = 0,0
  for e in d:
    l = sorted(d[e])
    if len(l)%2 == 0:
      for i in range(1,len(l),2):
        ans += (l[i] - l[i-1])//k
    else:
      v += 1
      if v>n%2:return -1
      le = len(l)
      p = [0]*le
      for i in range(2,le,2):
        p[i] = (l[i] - l[i-1])//k + p[i-2]
      ma,be,q = p[-1],0,float("inf")
      for i in range(le):
        if i%2:be += (l[i]-l[i-1])//k
        else:q = min(q,be + ma - p[i])
      ans += q
  return ans
for _ in range(int(input())):
  print(s())