Chef's dog Snuffles has so many things to play with! This time around, Snuffles has an array A containing N integers: A1, A2, ..., AN.
Bad news: Snuffles only loves to play with an array in which all the elements are equal.
Good news: We have a mover of size D. ! 
A mover of size D is a tool which helps to change arrays. Chef can pick two existing elements Ai and Aj from the array, such that i + D = j and subtract 1 from one of these elements (the element should have its value at least 1), and add 1 to the other element. In effect, a single operation of the mover, moves a value of 1 from one of the elements to the other.
Chef wants to find the minimum number of times she needs to use the mover of size D to make all the elements of the array A equal. Help her find this out.

-----Input-----
- The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two integers N and D, denoting the number of elements in the array and the size of the mover. 
- The second line of each testcase contains N space-separated integers: A1, A2, ..., AN, denoting the initial elements of the array. 

-----Output-----
- For each test case, output a single line containing the minimum number of uses or -1 if it is impossible to do what Snuffles wants.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- 1 ≤ D < N
- 1 ≤ Ai ≤ 109

-----Subtasks-----
- Subtask 1 (30 points) : N ≤  103
- Subtask 2 (70 points) : Original constraints

-----Example-----
Input:
3
5 2
1 4 5 2 3
3 1
1 4 1
4 2
3 4 3 5

Output:
3
2
-1

-----Explanation-----
Testcase 1:
Here is a possible sequence of usages of the mover:
- Move 1 from A3 to A1
- Move 1 from A3 to A1
- Move 1 from A2 to A4
At the end, the array becomes (3, 3, 3, 3, 3), which Snuffles likes. And you cannot achieve this in fewer moves. Hence the answer is 3.
Testcase 2:
Here is a possible sequence of usages of the mover:
- Move 1 from A2 to A1
- Move 1 from A2 to A3
At the end, the array becomes (2, 2, 2), which Snuffles likes. And you cannot achieve this in fewer moves. Hence the answer is 2.
Testcase 3:
It is impossible to make all the elements equal. Hence the answer is -1.

Difficulty: interview

Starter code:

Solutions:
tc=int(input())
for case in range(tc):
 n,d=list(map(int,input().split()))
 a=list(map(int,input().split()))
 sm=sum(a)
 f=True
 if sm%n==0:
  avg=sm/n
  for i in range(d):
   tmp_sm=0
   tmp_n=0
   for j in range(i,n,d):
    tmp_sm=tmp_sm+a[j]
    tmp_n+=1
   if tmp_sm%tmp_n==0:
    if avg!=tmp_sm/tmp_n:
     f=False
     break
   else:
    f=False
    break
 else:
  f=False
 if f:
  ans=0
  cur=0
  for i in range(d):
   for j in range(i,n,d):
    cur=cur+avg-a[j]
    ans=ans+abs(cur)
  print(ans)
 else:
  print(-1)


for _ in range(eval(input())):
 n, d = list(map(int, input().strip().split()))
 l = list(map(int, input().strip().split()))
 main_flag = 0
 final_count = 0
 total = sum(l)
 if total % n != 0:
  print(-1)
  continue
 else:
  expected_value = total / n
  for i in range(d):
   delta = []
   j = i
   while j < n:
    delta.append(expected_value - l[j])
    j += d
   diff = 0
   curr_diff = 0
   flag = 0
   count = 0
   for k in range(len(delta)):
    if diff != 0 and flag:
     count += abs(diff)
    if delta[k] != 0:
     diff += delta[k]
     if diff == 0:
      flag = 0
     else:
      flag = 1
   if flag == 0:
    final_count += count
   else:
    main_flag = 1
    break
 print(final_count if not main_flag else -1)


import sys
import string
import cmath
import math

T = int(input())
for i in range(T):
 N,D = list(map(int, input().split()))
 A = list(map(int, input().split()))
 s = sum(A)
 ans=0
 if (s%N)==0:
  x = s/N
  for j in range(N-D):
   if A[j]<x:
    A[j+D] -= x-A[j]
    ans+=x-A[j]
    A[j] = x
   elif A[j]>x:
    A[j+D] += A[j]-x
    ans+=A[j]-x
    A[j] = x
  for j in range(N):
   if A[j]!=x:
    ans=-1
 else:
  ans=-1
 
 print(ans)


T=int(input())
for i in range(0,T):
 (N,D)=input().split()
 N=int(N)
 D=int(D)
 L=[int(i) for i in input().split()]
 A=0
 flag=''
 MOVE=0
 s=0
 s=sum(L)
 if (s%len(L))!=0:
  print(-1)
  flag=False
 else:
  A=s/len(L)
  for i in range(N):
   if L[i]>A and (i+D)<N:
    diff=L[i]-A
    L[i]=L[i]-diff
    L[i+D]=L[i+D]+diff
    MOVE=MOVE+diff
    
   elif L[i]<A and (i+D)<N:
    diff=A-L[i]
    #if L[i+D]>=diff:
    L[i]=L[i]+diff
    L[i+D]=L[i+D]-diff
    MOVE=MOVE+diff
  for i in L:
   if i!=A and flag!=False:
    print(-1)
    flag=False
    break 
  if flag!=False:
   print(int(MOVE))
 

   
     


t=int(input())
 
while t>0:
 n,d = list(map(int, input().split()))
 arr=list(map(int, input().split()))
 count=0
 sum1=sum(arr)
 
 if sum1%n != 0:
  print("-1")

 else:
  ans=0
  average = sum1/n
  for i in range(0,n):
   if arr[i] != average and i+d>=n:
    ans=-1
    break
   else:
    y=arr[i]-average
    ans+=abs(y)
    if i+d < n:
     arr[i+d]+=y

     
  print(ans)
   
 t=t-1 


T=int(input())
for i in range(0,T):
 
 (N,D)=input().split()
 N=int(N)
 D=int(D)
 L=[int(i) for i in input().split()]
 A=0
 #A=sum(L)/float(len(L))
 #print A
 flag=''
 MOVE=0
 s=0
 s=sum(L)
 if (s%len(L))!=0:
  print(-1)
  flag=False
 else:
  A=s/len(L)
  for i in range(N):
   if L[i]>A and (i+D)<N:
    diff=L[i]-A
    L[i]=L[i]-diff
    L[i+D]=L[i+D]+diff
    MOVE=MOVE+diff
    
   elif L[i]<A and (i+D)<N:
    diff=A-L[i]
    #if L[i+D]>=diff:
    L[i]=L[i]+diff
    L[i+D]=L[i+D]-diff
    MOVE=MOVE+diff
  
  for i in L:
   if i!=A and flag!=False:
    print(-1)
    flag=False
    break
   
  if flag!=False:
   print(int(MOVE))
 

   
     


import sys

def solve():
 N,D = list(map(int,sys.stdin.readline().split()))
 A = list(map(int,sys.stdin.readline().split()))
 V = None
 M = 0
 for i in range(D):
  X = A[i::D]
  if sum(X)%len(X) != 0:
   return -1
  v = sum(X)/len(X)
  if V and V!=v:
   return -1
  for i in range(len(X)):
   c = X[i]-v
   M += abs(v-X[i])
   if i<len(X)-1:
    X[i+1] += c
 return M
T = int(sys.stdin.readline())

for _ in range(T):
 print(solve())

n = int(input())
 
while n != 0:
 no,b = list(map(int,input().split()))
 v = list(map(int,input().split()))
 number = sum(v)/no
 count = 0
 flag = True
 values = []
 if ((sum(v)%no) != 0) or (b > no):
  flag = False
 for i in range(b):
  vals = []
  for j in range(i,len(v),b):
   vals.append(v[j])
  values.append(vals)
 # print values
 for i in range(len(values)):
  if sum(values[i])/len(values[i]) != number:
   flag = False
 if flag:
  for i in range(no-b):
   y = v[i] - number
   v[i] -= y
   v[i+b] += y
   count += abs(y)
  
  print(count)
 else:
  print("-1")
 n = n - 1 

t=int(input())
for i0 in range(t):
 n,d=list(map(int,input().strip().split(' ')))
 a=list(map(int,input().strip().split(' ')))
 flag=0
 count=0
 if sum(a)%len(a)!=0:
  flag=1
 else:
  x=sum(a)/len(a)
  for i in range(len(a)-d):
   if flag!=1:
    if a[i]==x:
     pass
    elif a[i]<x:
     j=1
     y=x-a[i]
     while a[i]!=x:
      if a[i+(j*d)]-y>=0:
       a[i]=x
       a[i+(j*d)]-=y
       count+=j*y
       break
      if i+j*d<len(a):
       j+=1
      else:
       flag=1
       break
    else:
     if i+d<len(a):
      count+=a[i]-x
      a[i+d]+=a[i]-x
      a[i]=x
     else:
      flag=1
   else:
    break
 if a.count(x)!=len(a):
  flag=1
 if flag:
  print(-1)
 else:
  print(count) 

t=int(input())
for i0 in range(t):
 n,d=list(map(int,input().strip().split(' ')))
 a=list(map(int,input().strip().split(' ')))
 flag=0
 count=0
 if sum(a)%len(a)!=0:
  flag=1
 else:
  x=sum(a)/len(a)
  for i in range(len(a)-d):
   if flag!=1:
    if a[i]==x:
     pass
    elif a[i]<x:
     j=1
     y=x-a[i]
     while a[i]!=x:
      if a[i+(j*d)]-y>=0:
       a[i]=x
       a[i+(j*d)]-=y
       count+=j*y
       break
      if i+j*d<len(a):
       j+=1
      else:
       flag=1
       break
    else:
     if i+d<len(a):
      count+=a[i]-x
      a[i+d]+=a[i]-x
      a[i]=x
     else:
      flag=1
   else:
    break
 if a.count(x)!=len(a):
  flag=1
 if flag:
  print(-1)
 else:
  print(count) 

w=int(input())
def checkEqual(lst):
 return lst[1:] == lst[:-1]
v=0
while v<w:
 sign=0
 v+=1
 [n,d]=[int(i) for i in input().split()]
 arr=list(map(int , input().split()))
 #
 my_dict={}
 i=0
 while i<d:
  my_dict[i] = list()
  j=0
  while i+j<n:
   my_dict[i].append(arr[i+j])
   j+=d
  i+=1
 #check if mean of each list is same and equal to mean of arr and mean isnt a         float
 mean=float(sum(arr))/len(arr)
 if mean%1!=0.0:
  print(-1)
  continue
 else:
  means=[]
  for i in range(d):
   means.append((sum(my_dict[i])/len(my_dict[i])))
  if not(checkEqual(means)):
   print(-1)
   continue
  steps=0
  for x in range(d):
   for y in range(len(my_dict[x])):
     if (my_dict[x][y] < mean):
      steps += mean - my_dict[x][y]
      my_dict[x][y+1] -= mean - my_dict[x][y]
      my_dict[x][y] = mean
     elif (my_dict[x][y] > mean):
      steps += my_dict[x][y]-mean
      my_dict[x][y+1]+= my_dict[x][y] - mean
      my_dict[x][y] = mean
     elif (my_dict[x][y] == mean):
      continue
     else:
      print('impossible')
  print(int(steps))


t = eval(input())
for _ in range(t):
 n,d = list(map(int,input().split()))
 a = list(map(int,input().split()))
 avg = sum(a)/n
 res = 0
 
 for i in range(n-d):
  if a[i]<avg:
   diff = avg-a[i]
   a[i] += diff
   a[i+d] -= diff
   res += diff
  elif a[i]>avg:
   diff = a[i]-avg
   a[i] -= diff
   a[i+d] += diff
   res += diff
 flag = True
 for i in range(n):
  if a[i] != avg:
   flag = False
   break
 
 #print a
 if flag:
  print(res)
 else:
  print(-1)

#code

T = eval(input())

def is_equal(ar, D):
 N = len(ar)
 last = -1 
 for i in range(D):
  count = 0
  ans = 0
  for j in range(i, N, D):
   ans += ar[j]
   count += 1 
  if ans % count != 0:
   return -1 
  if last == -1:
   last = ans/count
  else:
   if last != ans/count:
    return -1 
 return last 
   
def solve(ar, D, equal):
 ans = 0
 N = len(ar) 
 for i in range(D):
  for j in range(i,N-D, D):
   diff = ar[j] - equal
   ar[j] -= diff 
   ar[j+D] += diff 
   ans += abs(diff)
 return ans 

for _ in range(T):
 N, D = list(map(int, input().split(" ")))
 ar = list(map(int, input().split(" ")))
 ans = is_equal(ar, D)
 if ans == -1:
  print(-1) 
 else:
  print(solve(ar,D,ans))

t = int(input())

while t!=0:
 n,d=list(map(int,input().strip().split()))
 a=input().strip()
 a= a.split()
 c=0
 b=[]
 c=sum(int(i) for i in a)
 
 if c%n!=0:
  print('-1')
 else:
  m=0
  b += n*[c/n]
  f=1
  for i in range(0,len(a)-d):
   if a.count(a[0]) == len(a):
    f=0
    break
   else:
    if int(a[i])>int(b[i]):
     temp=int(a[i])-int(b[i])
     a[i]=int(b[i])
     a[i+d]=int(a[i+d])+temp
     m=m+temp
    elif int(a[i])<int(b[i]):
     temp=int(b[i])-int(a[i])
     a[i]=int(b[i])
     a[i+d]=int(a[i+d])-temp
     m=m+temp
   if i==(len(a)-d-1) and all(int(x)==int(a[0]) for x in a):
    f=0
  if f==0:
   print(m)
  else:
   print('-1')
 t=t-1

#!/usr/bin/python
# coding: utf-8

t=int(input())
for i in range(t):
 (n,d)=list(map(int,input().split(' ')))
 arr=list(map(int,input().split(' ')))
 sum=0
 for j in arr:
  sum+=j
 if((sum%n)!=0):
  print("-1")
 else:
  tmp=0
  avg=sum/n
  num=[0]*d
  cnt=[0]*d
  for j in range(n):
   num[j%d]+=arr[j]
   cnt[j%d]+=1
  for j in range(d):
   if(num[j]%cnt[j]!=0 or num[j]/cnt[j]!=avg):
    tmp=1
    break
  if(tmp):
   print("-1")
  else:
   ans=0
   for j in range(n):
    if(arr[j]<avg):
     tmp=avg-arr[j]
     ind=j+d
     if(ind<n and arr[ind]>0):
      ans+=tmp
      arr[j]=avg
      arr[ind]-=tmp
    elif(arr[j]>avg):
     tmp=arr[j]-avg
     ind=j+d
     if(ind<n):
      ans+=tmp
      arr[j]=avg
      arr[ind]+=tmp
   print(ans)


'''

Chef's dog Snuffles has so many things to play with! This time around, Snuffles     has an array A containing N integers: A1, A2, ..., AN.

Bad news: Snuffles only loves to play with an array in which all the elements     are equal.

Good news: We have a mover of size D. !

A mover of size D is a tool which helps to change arrays. Chef can pick two     existing elements Ai and Aj from the array, such that i + D = j and subtract     1 from one of these elements 
(the element should have its value at least 1), and add 1 to the other element.     In effect, a single operation of the mover, moves a value of 1 from one of     the elements to the other.

Chef wants to find the minimum number of times she needs to use the mover of     size D to make all the elements of the array A equal. Help her find this out    .

Input
The first line of the input contains an integer T, denoting the number of test     cases. The description of T test cases follows.
The first line of each test case contains two integers N and D, denoting the     number of elements in the array and the size of the mover.
The second line of each testcase contains N space-separated integers: A1, A2,     ..., AN, denoting the initial elements of the array.

Output
For each test case, output a single line containing the minimum number of uses     or -1 if it is impossible to do what Snuffles wants.

Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
1 ≤ D < N
1 ≤ Ai ≤ 10^9

Subtasks
Subtask 1 (30 points) : N ≤ 10^3
Subtask 2 (70 points) : Original constraints

Example
Input:
3
5 2
1 4 5 2 3
3 1
1 4 1
4 2
3 4 3 5

Output:
3
2
-1

Explanation
Testcase 1:
Here is a possible sequence of usages of the mover:
Move 1 from A3 to A1
Move 1 from A3 to A1
Move 1 from A2 to A4
At the end, the array becomes (3, 3, 3, 3, 3), which Snuffles likes. And you     cannot achieve this in fewer moves. Hence the answer is 3.

Testcase 2:
Here is a possible sequence of usages of the mover:
Move 1 from A2 to A1
Move 1 from A2 to A3
At the end, the array becomes (2, 2, 2), which Snuffles likes. And you cannot     achieve this in fewer moves. Hence the answer is 2.

Testcase 3:
It is impossible to make all the elements equal. Hence the answer is -1.

'''


#!/usr/bin/python
# coding: utf-8

t=int(input())
for i in range(t):
 (n,d)=list(map(int,input().split(' ')))
 arr=list(map(int,input().split(' ')))
 sum=0
 for j in arr:
  sum+=j
 if((sum%n)!=0):
  print("-1")
 else:
  tmp=0
  avg=sum/n
  num=[0]*d
  cnt=[0]*d
  for j in range(n):
   num[j%d]+=arr[j]
   cnt[j%d]+=1
  for j in range(d):
   if(num[j]%cnt[j]!=0 or num[j]/cnt[j]!=avg):
    tmp=1
    break
  if(tmp):
   print("-1")
  else:
   ans=0
   for j in range(n):
    if(arr[j]<avg):
     tmp=avg-arr[j]
     ind=j+d
     if(ind<n and arr[ind]>0):
      ans+=tmp
      arr[j]=avg
      arr[ind]-=tmp
    elif(arr[j]>avg):
     tmp=arr[j]-avg
     ind=j+d
     if(ind<n):
      ans+=tmp
      arr[j]=avg
      arr[ind]+=tmp
   print(ans)


t = int(input())

for _ in range(t):
 N, D = list(map(int, input().split()))
 L = list(map(int, input().split()))
 flag = True
 avg = None
 for x in range(D):
  temp = x
  sumA = L[x]
  numElem = 1
  while temp+D<N:
   numElem+=1
   sumA+=L[temp+D]
   temp+=D
   
  if sumA%numElem:
   flag = False
   break
   
  
  if avg==None:
   avg = sumA/numElem
  elif avg!=(sumA/numElem):
   flag = False
   break
   
  
 if flag:
  res = 0
  tempDiff = 0
  for x in range(D):
   temp = x 
   tempDiff = L[x]-avg
   while temp+D<N:
    L[temp+D]+=tempDiff
    if tempDiff<0:
     res-=tempDiff
    else:
     res+=tempDiff
    temp+=D
    tempDiff = L[temp]-avg
    
  print(res)
    
 else:
  print(-1)

def main():
 t=eval(input())
 while t>0:
  n,d=list(map(int,input().split()))
  l=list(map(int,input().split()))
  count=0
  k=sum(l)
  if k%n!=0:
   print("-1")
  else:
   r=sum(l)/n
   for i in range(n-d):
    if l[i]<r:
     count+=r-l[i]
     l[i+d]-=r-l[i]
     l[i]=r
    else:
     count+=l[i]-r
     l[i+d]+=l[i]-r
     l[i]=r
   if l.count(r)==n:
    print(count)
   else:
    print("-1")
  t-=1 
main()

t = int(input())

for _ in range(t):
 N, D = list(map(int, input().split()))
 L = list(map(int, input().split()))
 flag = True
 avg = None
 for x in range(D):
  temp = x
  sumA = L[x]
  numElem = 1
  while temp+D<N:
   numElem+=1
   sumA+=L[temp+D]
   temp+=D
   
  if sumA%numElem:
   flag = False
   break
   
  
  if avg==None:
   avg = sumA/numElem
  elif avg!=(sumA/numElem):
   flag = False
   break
   
  
 if flag:
  res = 0
  tempDiff = 0
  for x in range(D):
   temp = x 
   tempDiff = L[x]-avg
   while temp+D<N:
    L[temp+D]+=tempDiff
    if tempDiff<0:
     res-=tempDiff
    else:
     res+=tempDiff
    temp+=D
    tempDiff = L[temp]-avg
    
  print(res)
    
 else:
  print(-1)



t = eval(input())

for _ in range(t):
 n, d = list(map(int, input().split()))
 a = list(map(int, input().split()))
 s = sum(a)

 if s%n != 0:
  print(-1)
  continue

 each = s/n

 ans, ok = 0, True
 for i in range(d):

  cur, rem = i, 0
  while cur < n: 
   rem = a[cur]+rem-each
   ans += abs(rem)
   cur += d

  if rem != 0:
   ok = False
   break

 print(ans if ok else -1)


import sys

t = int(sys.stdin.readline().strip())

while t:

 n, d = list(map(int, sys.stdin.readline().strip().split(" ")))
 nums = list(map(int, sys.stdin.readline().strip().split(" ")))
 a = False
 s = 0
 for i in nums:
  s = s + i
 avg = s//n
 ans = 0
 count = 0
 if s%n != 0:
  ans = -1
 else:
  arr = [avg]*n
  
  for i in range(len(arr)-d):
   k = arr[i] - nums[i]
   if k!=0:
    arr[i] = arr[i] - k
    arr[i+d] = arr[i+d] + k
    count += abs(k)
  for i in range(len(arr)):
   if arr[i] != nums[i]:
    ans = -1
    a = True
    break

  if a != True:
   ans = count
 print(ans)
 t-=1