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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#!/usr/bin/python\n# coding: utf-8\n\nt=int(input())\nfor i in range(t):\n (n,d)=list(map(int,input().split(\' \')))\n arr=list(map(int,input().split(\' \')))\n sum=0\n for j in arr:\n  sum+=j\n if((sum%n)!=0):\n  print("-1")\n else:\n  tmp=0\n  avg=sum/n\n  num=[0]*d\n  cnt=[0]*d\n  for j in range(n):\n   num[j%d]+=arr[j]\n   cnt[j%d]+=1\n  for j in range(d):\n   if(num[j]%cnt[j]!=0 or num[j]/cnt[j]!=avg):\n    tmp=1\n    break\n  if(tmp):\n   print("-1")\n  else:\n   ans=0\n   for j in range(n):\n    if(arr[j]<avg):\n     tmp=avg-arr[j]\n     ind=j+d\n     if(ind<n and arr[ind]>0):\n      ans+=tmp\n      arr[j]=avg\n      arr[ind]-=tmp\n    elif(arr[j]>avg):\n     tmp=arr[j]-avg\n     ind=j+d\n     if(ind<n):\n      ans+=tmp\n      arr[j]=avg\n      arr[ind]+=tmp\n   print(ans)\n\n\n\'\'\'\n\nChef\'s dog Snuffles has so many things to play with! This time around, Snuffles \xa0\xa0\xa0\xa0has an array A containing N integers: A1, A2, ..., AN.\n\nBad news: Snuffles only loves to play with an array in which all the elements \xa0\xa0\xa0\xa0are equal.\n\nGood news: We have a mover of size D. !\n\nA mover of size D is a tool which helps to change arrays. Chef can pick two \xa0\xa0\xa0\xa0existing elements Ai and Aj from the array, such that i + D = j and subtract \xa0\xa0\xa0\xa01 from one of these elements \n(the element should have its value at least 1), and add 1 to the other element. \xa0\xa0\xa0\xa0In effect, a single operation of the mover, moves a value of 1 from one of \xa0\xa0\xa0\xa0the elements to the other.\n\nChef wants to find the minimum number of times she needs to use the mover of \xa0\xa0\xa0\xa0size D to make all the elements of the array A equal. Help her find this out\xa0\xa0\xa0\xa0.\n\nInput\nThe first line of the input contains an integer T, denoting the number of test \xa0\xa0\xa0\xa0cases. The description of T test cases follows.\nThe first line of each test case contains two integers N and D, denoting the \xa0\xa0\xa0\xa0number of elements in the array and the size of the mover.\nThe second line of each testcase contains N space-separated integers: A1, A2, \xa0\xa0\xa0\xa0..., AN, denoting the initial elements of the array.\n\nOutput\nFor each test case, output a single line containing the minimum number of uses \xa0\xa0\xa0\xa0or -1 if it is impossible to do what Snuffles wants.\n\nConstraints\n1 ≤ T ≤ 10\n2 ≤ N ≤ 10^5\n1 ≤ D < N\n1 ≤ Ai ≤ 10^9\n\nSubtasks\nSubtask 1 (30 points) : N ≤ 10^3\nSubtask 2 (70 points) : Original constraints\n\nExample\nInput:\n3\n5 2\n1 4 5 2 3\n3 1\n1 4 1\n4 2\n3 4 3 5\n\nOutput:\n3\n2\n-1\n\nExplanation\nTestcase 1:\nHere is a possible sequence of usages of the mover:\nMove 1 from A3 to A1\nMove 1 from A3 to A1\nMove 1 from A2 to A4\nAt the end, the array becomes (3, 3, 3, 3, 3), which Snuffles likes. And you \xa0\xa0\xa0\xa0cannot achieve this in fewer moves. Hence the answer is 3.\n\nTestcase 2:\nHere is a possible sequence of usages of the mover:\nMove 1 from A2 to A1\nMove 1 from A2 to A3\nAt the end, the array becomes (2, 2, 2), which Snuffles likes. And you cannot \xa0\xa0\xa0\xa0achieve this in fewer moves. Hence the answer is 2.\n\nTestcase 3:\nIt is impossible to make all the elements equal. Hence the answer is -1.\n\n\'\'\'\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13705