Read problems statements in mandarin chinese, russian and vietnamese as well. 

Chef's dog Snuffles has so many things to play with! This time around, Snuffles has an array A containing N integers: A_{1}, A_{2}, ..., A_{N}. 

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 A_{i} and A_{j} 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: A_{1}, A_{2}, ..., A_{N}, 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 ≤ A_{i} ≤ 10^{9}$

------ Subtasks ------ 

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

----- Sample Input 1 ------ 
3

5 2

1 4 5 2 3

3 1

1 4 1

4 2

3 4 3 5
----- Sample Output 1 ------ 
3

2

-1
----- explanation 1 ------ 
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: MEDIUM_HARD

Starter code:

Solutions:
for _ in range(int(input())):
	(N, D) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = sum(arr)
	if total % len(arr) != 0:
		print(-1)
	else:
		div = total // len(arr)
		j = 0
		count = 0
		while j + D < len(arr):
			if arr[j] < div:
				diff = div - arr[j]
				count += diff
				arr[j] += diff
				arr[j + D] -= diff
			elif arr[j] > div:
				diff = arr[j] - div
				count += diff
				arr[j] -= diff
				arr[j + D] += diff
			j += 1
		while j < len(arr):
			if arr[j] != div:
				count = -1
				break
			j += 1
		print(count)


import sys
import math as mp
for _ in range(int(sys.stdin.readline())):
	(n, d) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	t = sum(l) / len(l)
	f = 0
	l1 = 0
	w = []
	if mp.ceil(t) != mp.floor(t):
		sys.stdout.write('-1' + '\n')
		continue
	else:
		t = int(t)
		for i in range(len(l)):
			w.append(t - l[i])
		e = 0
		for i in range(d):
			ct = 0
			for ii in range(i, n, d):
				ct += w[ii]
				f += abs(ct)
			if ct != 0:
				l1 = 1
		if l1 == 0:
			sys.stdout.write(str(f) + '\n')
		else:
			sys.stdout.write('-1' + '\n')


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	if sum(a) % n != 0:
		print(-1)
	else:
		avg = sum(a) // n
		ans = 0
		for i in range(n - d):
			t = abs(a[i] - avg)
			ans += abs(a[i] - avg)
			if a[i] > avg:
				a[i] = avg
				a[i + d] = a[i + d] + 1 * t
			elif a[i] < avg:
				a[i] = avg
				a[i + d] = a[i + d] - 1 * t
		if a.count(a[0]) == n:
			print(ans)
		else:
			print(-1)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	f = 1
	l = [int(i) for i in input().split()]
	if sum(l) % n != 0:
		print(-1)
	else:
		ans = 0
		av = sum(l) // n
		for i in range(d):
			p = 0
			for j in range(i, n, d):
				p += l[j] - av
				ans += abs(p)
			if p != 0:
				f = 0
				break
		if f:
			print(ans)
		else:
			print(-1)


def avg(lst):
	return sum(lst) / len(lst)

def noturns(lst, mean):
	ret = 0
	for x in range(len(lst)):
		if x != len(lst) - 1:
			lst[x + 1] = lst[x] - mean + lst[x + 1]
			ret = ret + abs(lst[x] - mean)
			lst[x] = mean
	return ret
t = int(input())
while t > 0:
	(i, d) = map(int, input().split())
	set = [int(s) for s in input().split()]
	mean = avg(set)
	answer = 0
	for x in range(d):
		test = set[x::d]
		tmean = avg(test)
		if tmean == mean:
			answer = answer + noturns(test, mean)
		else:
			answer = -1
			break
	print(round(answer))
	t = t - 1


t = int(input())
for z in range(t):
	(n, d) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	s = sum(a) // n
	flag = 0
	ans = 0
	for i in range(n - d):
		if a[i] > s:
			a[i + d] += a[i] - s
			ans += a[i] - s
			a[i] = s
		else:
			a[i + d] -= s - a[i]
			ans += s - a[i]
			a[i] = s
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		print(ans)


t = int(input(''))
for xxx in range(t):
	s = input('').split(' ')
	(n, d, s, c) = (int(s[0]), int(s[1]), 0, 0)
	a = input('').split(' ')
	for i in range(n):
		a[i] = int(a[i])
	if sum(a) % n == 0:
		x = sum(a) / n
		for l in range(n - d):
			if a[l] < x:
				b = x - a[l]
				c += b
				a[l] = x
				a[l + d] -= b
			elif a[l] > x:
				b = a[l] - x
				c += b
				a[l] = x
				a[l + d] += b
		for l in range(n):
			if a[l] != x:
				s = 1
				break
		if s == 1:
			print(-1)
		else:
			print(int(c))
	else:
		print(-1)


t = int(input())
for i in range(t):
	(N, D) = map(int, input().split())
	x = input()
	x = x.split()
	a = []
	s = 0
	c = 0
	for j in range(N):
		a.append(int(x[j]))
	total = sum(a)
	if total % N == 0:
		x = total // N
		for l in range(N - D):
			if a[l] < x:
				b = x - a[l]
				c = c + b
				a[l] = x
				a[l + D] = a[l + D] - b
			elif a[l] > x:
				b = a[l] - x
				c = c + b
				a[l] = x
				a[l + D] = a[l + D] + b
		for k in range(N):
			if a[k] != x:
				s = 1
				break
		if s == 1:
			print(-1)
		else:
			print(c)
	else:
		print(-1)


for t in range(int(input())):
	(n, d) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	if sum(a) % n != 0:
		print(-1)
	else:
		p = sum(a[:]) // n
		ct = 0
		for i in range(n - d):
			if a[i] < p:
				a[i + d] -= p - a[i]
				ct += p - a[i]
				a[i] = p
			elif a[i] > p:
				a[i + d] += a[i] - p
				ct += a[i] - p
				a[i] = p
		if max(a) == min(a):
			print(ct)
		else:
			print(-1)


for i in range(int(input())):
	(n, d) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	avg = sum(a) // n
	c = -1
	done = 0
	f = 0
	ans = 0
	if sum(a) % n != 0:
		print(-1)
		continue
	for i in a:
		c += 1
		if c + d < n:
			if i > avg:
				diff = i - avg
				a[c + d] += diff
				a[c] -= diff
				ans += diff
			elif i < avg:
				diff = avg - i
				a[c] += diff
				a[c + d] -= diff
				ans += diff
		else:
			break
	if len(set(a)) == 1:
		print(int(ans))
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	tb = 0
	e = 0
	s = []
	for j in range(d):
		su = 0
		c = 0
		for k in range(j, n, d):
			su = su + a[k]
			c = c + 1
		if su / c != su // c:
			e = 1
			break
		s.append(su // c)
	if e == 1:
		print(-1)
	else:
		for j in range(d):
			for k in range(j, n - d, d):
				if a[k] > s[j]:
					extra = a[k] - s[j]
					a[k] = s[j]
					a[k + d] = a[k + d] + extra
					tb = tb + extra
				elif a[k] < s[j]:
					extra = s[j] - a[k]
					a[k] = s[j]
					a[k + d] = a[k + d] - extra
					tb = tb + extra
		print(tb)


from math import sqrt
import sys
t = int(input())
while t:
	flag = 0
	(n, d) = map(int, sys.stdin.readline().split())
	arr = list(map(int, input().split()))
	c = 0
	diff = 0
	avg = sum(arr)
	x = avg // n
	for i in range(0, n - d):
		j = i + d
		if arr[i] < x:
			diff = x - arr[i]
			arr[i] = x
			arr[j] -= diff
			c += diff
		elif arr[i] > x:
			diff = arr[i] - x
			arr[j] += diff
			arr[i] = x
			c += diff
	if len(set(arr)) == 1:
		print(c)
	else:
		print(-1)
	t = t - 1


import math
import statistics
for t in range(int(input())):
	(n, d) = map(int, input('').split())
	a = list(map(int, input('').split()))
	count = 0
	i = 0
	mn = statistics.mean(a)
	if math.floor(mn) != math.ceil(mn):
		print(-1)
		continue
	else:
		while count < n - d:
			difference = abs(a[count] - mn)
			if a[count] < mn:
				a[count + d] -= difference
				a[count] += difference
				i += difference
			else:
				a[count] -= difference
				a[count + d] += difference
				i += difference
			count += 1
		if len(set(a)) == 1:
			print(i)
		else:
			print(-1)


for case in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	v = s // n
	o = 0
	for i in range(n - d):
		if a[i] > v:
			o += a[i] - v
			a[i + d] += a[i] - v
			a[i] = v
		elif a[i] < v:
			o += v - a[i]
			a[i + d] -= v - a[i]
			a[i] = v
	if len(set(a)) == 1:
		print(o)
	else:
		print(-1)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	f = 0
	sum = 0
	for x in a:
		sum += x
	if sum % n:
		f = 1
	else:
		avg = sum // n
		c = 0
		for i in range(d):
			(cur, rem) = (i, 0)
			while cur < n:
				rem = a[cur] + rem - avg
				c += abs(rem)
				cur += d
			if rem != 0:
				f = 1
				break
	print(c if not f else -1)


import math
for ii in range(int(input())):
	n = [int(x) for x in input().split()]
	s = 0
	l = [int(x) for x in input().split()]
	for i in range(n[0]):
		s = s + l[i]
	m = s / n[0]
	if int(m) != m:
		print('-1')
	else:
		k = 0
		c = 0
		m = int(m)
		for i in range(n[0] - n[1]):
			if l[i] > m:
				p = l[i] - m
				l[i] = m
				l[i + n[1]] = l[i + n[1]] + p
				c = c + p
			elif l[i] < m:
				p = m - l[i]
				l[i] = m
				l[i + n[1]] = l[i + n[1]] - p
				c = c + p
		for i in range(n[0]):
			if l[i] != m:
				k = 1
				break
		if k == 1:
			print('-1')
		else:
			print(c)


def moveOnce(arr, d, avg):
	total = 0
	done = True
	for i in range(len(arr) - d):
		if arr[i] == avg:
			continue
		elif arr[i] > avg:
			total += arr[i] - avg
			arr[i + d] += arr[i] - avg
			arr[i] = avg
		else:
			moves = avg - arr[i]
			if moves > arr[i + d]:
				moves = arr[i + d]
			total += moves
			arr[i] += moves
			arr[i + d] -= moves
			if arr[i] != avg:
				done = False
	for i in range(len(arr) - d, len(arr)):
		if arr[i] != avg:
			done = False
			break
	return (total, done)

def mover(arr, d):
	s = sum(arr)
	avg = s // len(arr)
	if avg * len(arr) != s:
		return -1
	total = 0
	done = False
	while done == False:
		(s, done) = moveOnce(arr, d, avg)
		total += s
		if done:
			return total
		elif s == 0:
			return -1

def validate(arr, d):
	avg = -1
	for i in range(d):
		count = 0
		total = 0
		for j in range(i, len(arr), d):
			count += 1
			total += arr[j]
		avg1 = total // count
		if avg1 * count != total:
			return False
		if avg < 0:
			avg = avg1
		elif avg != avg1:
			return False
	return True

def mover2(arr, d):
	if validate(arr, d) == False:
		return -1
	s = sum(arr)
	avg = s // len(arr)
	ans = 0
	for i in range(d):
		for j in range(i, len(arr), d):
			if arr[j] == avg:
				continue
			elif arr[j] > avg:
				ans += arr[j] - avg
				arr[j + d] += arr[j] - avg
				arr[j] = avg
			else:
				diff = avg - arr[j]
				ans += diff
				arr[j + d] -= diff
				arr[j] = avg
	return ans

def test():
	print(mover2([1, 4, 5, 2, 3], 2))
	print(mover2([11, 4, 5, 2, 3], 1))
	print(mover2([1, 4, 1], 1))
	print(mover2([4, 1, 1], 1))
	print(mover2([3, 4, 3, 5], 2))
	print(mover2([1, 2, 5, 2, 5], 2))
	print(mover2([1, 1, 5, 3, 5], 1))
	print(mover2([1, 3, 3, 3, 5], 4))
	print(mover2([2100000000, 2000000000, 2000000001, 30, 4], 1))
	print(mover2([1, 3], 1))
	print(mover2([1, 1], 1))
	print(mover2([1, 1, 1], 2))
	print(mover2([1, 2, 3], 2))
	print(mover2([1, 2, 6], 2))
	print(mover2([1, 5, 6], 2))
	print(mover2([100000000, 500000000, 800000000, 700000000, 600000000, 400000000, 1000000000, 700000000, 600000000], 3))

def ni():
	s = input()
	while len(s) == 0:
		s = input()
	try:
		return int(s)
	except:
		return 0

def nia():
	s = input()
	while len(s) == 0:
		s = input()
	s = s.split()
	iVal = []
	for i in range(len(s)):
		iVal.append(int(s[i]))
	return iVal

def solve():
	T = ni()
	for t in range(T):
		ND = nia()
		arr = nia()
		print(mover2(arr, ND[1]))
solve()


import math
import statistics
N = int(input())
for m in range(N):
	(temp, newOne) = map(int, input().split())
	l = list(map(int, input().split()))
	mn = statistics.mean(l)
	i = 0
	if math.floor(mn) != math.ceil(mn):
		print(-1)
		continue
	else:
		z = 0
		while z < temp - newOne:
			difference = abs(l[z] - mn)
			if l[z] > mn:
				l[z] -= difference
				l[z + newOne] += difference
				i += difference
			else:
				l[z] += difference
				l[z + newOne] -= difference
				i += difference
			z += 1
		if len(set(l)) == 1:
			print(i)
		else:
			print(-1)


import math
import statistics
N = int(input())
for m in range(N):
	(x, d) = map(int, input().split())
	l = list(map(int, input().split()))
	data = statistics.mean(l)
	i = 0
	if math.floor(data) != math.ceil(data):
		print(-1)
		continue
	else:
		z = 0
		while z < x - d:
			difference = abs(l[z] - data)
			if l[z] > data:
				l[z] -= difference
				l[z + d] += difference
				i += difference
			else:
				l[z] += difference
				l[z + d] -= difference
				i += difference
			z += 1
		if len(set(l)) == 1:
			print(i)
		else:
			print(-1)


t = int(input())
for r in range(t):
	(n, d) = map(int, input().strip().split())
	a = list(map(int, input().strip().split(' ')))
	vs = [0] * d
	cd = [0] * d
	for i in range(n):
		vs[i % d] += a[i]
		cd[i % d] += 1
	rv = vs[0] / cd[0]
	fl = True
	for i in range(d):
		if rv == vs[i] / cd[i]:
			continue
		else:
			fl = False
			break
	val = int(rv)
	if fl and float(val) == rv:
		ans = 0
		for j in range(d):
			for i in range(j, n, d):
				if i + d < n:
					if a[i] < val:
						a[i + d] = a[i + d] - (val - a[i])
						ans += val - a[i]
						a[i] = val
					elif a[i] > val:
						a[i + d] = a[i + d] + (a[i] - val)
						ans += a[i] - val
						a[i] = val
		print(ans)
	else:
		print(-1)


import sys
n = int(input().strip())
for i in range(0, n):
	a = [int(scores_temp) for scores_temp in input().strip().split(' ')]
	b = [int(scores_temp) for scores_temp in input().strip().split(' ')]
	br = moves = 0
	s = sum(b)
	t = int(s / a[0])
	for j in range(0, a[1]):
		o = j
		dabbe = su = 0
		for l in range(j, a[0]):
			if o >= a[0]:
				break
			su = su + b[o]
			o = o + a[1]
			dabbe = dabbe + 1
		if su % dabbe != 0 and su / dabbe != t:
			br = 1
			break
	if br == 1:
		print(-1)
	else:
		for i in range(0, a[0] - a[1]):
			x = abs(t - b[i])
			if b[i] <= b[i + a[1]]:
				if b[i] < t:
					b[i] = b[i] + x
					b[i + a[1]] = b[i + a[1]] - x
					moves = moves + x
				else:
					b[i] = b[i] - x
					b[i + a[1]] = b[i + a[1]] + x
					moves = moves + x
			elif b[i] > b[i + a[1]]:
				if b[i] > t:
					b[i] = b[i] - x
					b[i + a[1]] = b[i + a[1]] + x
					moves = moves + x
				else:
					b[i] = b[i] + x
					b[i + a[1]] = b[i + a[1]] - x
					moves = moves + x
		if min(b) == max(b):
			print(moves)
		else:
			print(-1)


import numpy as np
t = int(input())
for pq in range(t):
	t1 = list(map(int, input().split()))
	n = t1[0]
	d = t1[1]
	arr = list(map(int, input().split()))
	m = np.mean(arr)
	x = int(m)
	cnt = 0
	if m % x == 0:
		for i in range(d):
			li = arr[i::d]
			for k in range(len(li) - 1):
				li[k + 1] -= x - li[k]
				cnt += abs(x - li[k])
			if li[-1] != x:
				print(-1)
				break
		else:
			print(cnt)
	else:
		print(-1)


import math
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	array = list(map(int, input().split()))
	steps = 0
	avg = sum(array) / len(array)
	if avg != math.floor(avg):
		print(-1)
		continue
	else:
		avg = int(avg)
		for i in range(n - d):
			diff = 0
			if array[i] < avg:
				diff = avg - array[i]
				array[i] += diff
				array[i + d] -= diff
			elif array[i] > avg:
				diff = array[i] - avg
				array[i] = array[i] - diff
				array[i + d] = array[i + d] + diff
			steps += diff
	if len(set(array)) != 1:
		print(-1)
	else:
		print(int(steps))


for test in range(int(input())):
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	target = sum(arr) / n
	count = 0
	if int(target) < target:
		print(-1)
		continue
	else:
		target = int(target)
		for i in range(n):
			if i + d >= n:
				if arr[i] != target:
					count = -1
					break
			elif arr[i] != target:
				diff = int(arr[i] - target)
				arr[i] = target
				arr[i + d] += diff
				count += abs(diff)
		if set(arr) != {target}:
			print(-1)
		else:
			print(count)


def mover(ar, n, d):
	totalsum = sum(ar)
	i = 0
	avg = totalsum / n
	(p, count) = (0, 0)
	while p < d:
		for j in range(p + d, n, d):
			if ar[j - d] < avg:
				count += avg - ar[j - d]
				ar[j] -= avg - ar[j - d]
				ar[j - d] = avg
			if ar[j - d] > avg:
				count += ar[j - d] - avg
				ar[j] += ar[j - d] - avg
				ar[j - d] = avg
		p += 1
	return [count, ar]
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().strip().split(' '))
	a = list(map(int, input().strip().split(' ')))
	(ans, a) = mover(a, n, d)
	if 1 <= t <= 10 and 2 <= n <= 100000.0 and (1 <= d < n):
		if len(set(a)) == 1:
			print(int(ans))
		else:
			print(-1)


def main():
	for i in range(int(input())):
		brr = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		(q, p, count) = (0, 0, 0)
		(n, d) = (brr[0], brr[1])
		for i in range(n):
			q += arr[i]
		if q % n != 0:
			flag = 1
		else:
			p = q // n
			i = 0
			while i < d:
				k = i
				temp = 0
				while k < n:
					temp += arr[k] - p
					k += d
				if temp != 0:
					flag = 1
					break
				else:
					flag = 0
				i += 1
		k = 0
		if flag == 0:
			while k < d:
				j = k
				while j < n - d:
					if arr[j] > p:
						count += arr[j] - p
						arr[j + d] += arr[j] - p
					else:
						i = j
						while arr[i] < p and i < n:
							i += d
						count += (i - j) // d * (p - arr[j])
						arr[i] -= p - arr[j]
					j += d
				k += 1
		if flag == 1:
			print('-1')
		else:
			print(count)
main()


for _ in range(int(input())):
	flag = 0
	(N, d) = map(int, input().split())
	s = list(map(int, input().split()))
	count = 0
	m = 0
	for l in range(N):
		m = m + s[l]
	if m % len(s) != 0:
		print('-1')
	else:
		flag = 0
		x = m / len(s)
		for a in range(d):
			k = 0
			p = 0
			z = a
			while z < N:
				k += s[z]
				p += 1
				z += d
			if k % p == 0 and k / p == x:
				flag = 0
			else:
				flag = 1
				break
		if flag == 1:
			print('-1')
		else:
			for i in range(d):
				c = 1
				j = i
				sum = 0
				while j < N:
					sum = sum + s[j]
					count += abs(x * c - sum)
					j += d
					c += 1
			print(int(count))


t = int(input())
while t > 0:
	t -= 1
	(n, d) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	carr = [int(x) for x in arr]
	arr_sum = sum(arr)
	if arr_sum % n != 0:
		print('-1')
		continue
	num = int(arr_sum / n)
	status = True
	count = 0
	for i in range(0, n):
		if i + d < n:
			x = num - arr[i]
			arr[i] = num
			count += abs(x)
			arr[i + d] += -x
	for ii in range(0, n):
		if arr[ii] != num:
			status = False
	if not status:
		print('-1')
	else:
		print(count)


tc = int(input())
while tc:
	(n, d) = map(int, input().split())
	str = list(map(int, input().split()))
	avg = sum(str) / float(n)
	iavg = int(avg)
	cnt = 0
	flag = 1
	if iavg == avg:
		for j in range(0, n - d, d):
			for i in range(j, min(j + d, n - d)):
				diff = str[i] - iavg
				str[i] = iavg
				str[i + d] += diff
				cnt += abs(diff)
	for x in str:
		if x != iavg:
			flag = 0
			break
	if flag == 0:
		print('-1')
	else:
		print(cnt)
	tc -= 1


for t in range(int(input())):
	(N, D) = map(int, input().split())
	n = list(map(int, input().split()))
	avg = sum(n) / N
	s = 0
	if int(avg) == avg:
		avg = int(avg)
		for m in range(D):
			i = m
			r = 0
			z = n[i::D]
			navg = sum(z) / len(z)
			if avg == navg:
				for x in z:
					x = x + r
					r = x - avg
					s = s + abs(r)
			else:
				print(-1)
				break
		else:
			print(s)
	else:
		print(-1)


for z in range(int(input())):
	(length, D) = input().split()
	list_1 = list(map(int, input().strip().split()))
	passes = 0
	avg = sum(list_1) / int(length)
	if avg != int(avg):
		passes = -1
	else:
		for i in range(int(length) - int(D)):
			list_1[i + int(D)] += list_1[i] - avg
			passes += abs(list_1[i] - avg)
			list_1[i] = avg
		for q in range(int(length)):
			if list_1[q] != avg:
				passes = -1
				break
	print(int(passes))


x = int(input())
for i in range(x):
	(a, b) = map(int, input().strip().split(' '))
	l = [int(a) for a in input().strip().split(' ')]
	s = sum(l)
	arr = [0] * a
	ind = []
	flag = 0
	su = 0
	if s % a != 0:
		flag = 1
	else:
		num = s // a
	if flag != 1:
		c = 0
		for j in range(a - b):
			if l[j] > num:
				diff = l[j] - num
				l[j] = num
				l[j + b] += diff
				su += diff
			elif l[j] < num:
				diff = num - l[j]
				l[j] = num
				l[j + b] -= diff
				su += diff
		if len(set(l)) != 1:
			flag = 1
	if flag == 1:
		print(-1)
	else:
		print(su)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	c = 0
	for k in l:
		s = s + k
	if s % n == 0:
		for k in range(d):
			for j in range(k, n - d, d):
				if l[j] < s / n:
					c = s / n - l[j] + c
					h = s / n - l[j]
					l[j] = l[j] + h
					l[j + d] = l[j + d] - h
				if l[j] > s / n:
					c = c + (l[j] - s / n)
					h = l[j] - s / n
					l[j] = l[j] - h
					l[j + d] = l[j + d] + h
		if l.count(s / n) == n:
			print(int(c))
		else:
			print(-1)
	else:
		print(-1)


from math import *

def fonction(tab, taille, mover):
	moy = sum(tab)
	if moy % taille != 0:
		return -1
	moy //= taille
	OP = 0
	Mat = []
	defaut = []
	dispo = []
	somme = [0] * mover
	for i in range(mover):
		tmp = []
		tmp_def = []
		tmp_disp = []
		for j in range(i, taille, mover):
			tmp.append(tab[j])
			somme[i] += tab[j]
			if tab[j] > moy:
				tmp_disp.append([tab[j] - moy, j // mover])
			elif tab[j] < moy:
				tmp_def.append([moy - tab[j], j // mover])
		if moy * ((taille - i - 1) // mover + 1) != somme[i]:
			return -1
		defaut.append(tmp_def)
		dispo.append(tmp_disp)
		Mat.append(tmp)
	for i in range(mover):
		ind_disp = 0
		for j in range(len(defaut[i])):
			k = ind_disp
			while defaut[i][j][0] > 0:
				t = min(defaut[i][j][0], dispo[i][k][0])
				defaut[i][j][0] -= t
				dispo[i][k][0] -= t
				if dispo[i][k][0] == 0:
					ind_disp = k + 1
				OP += t * fabs(defaut[i][j][1] - dispo[i][k][1])
				k += 1
	return int(OP)
N = int(input())
for a in range(N):
	(taille, d) = (int(i) for i in input().split())
	tab = [int(i) for i in input().split()]
	print(fonction(tab, taille, d))


output = []
T = int(input())
for i in range(0, T):
	(N, D) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	avg = sum(arr) / len(arr)
	if avg - int(avg) != 0:
		output.append(-1)
	elif D > N / 2 and any((spectator != avg for spectator in arr[N - D:D])):
		output.append(-1)
	else:
		groups = []
		group_avgs = []
		if D < N / 2:
			group_starter_max = D - 1
		else:
			group_starter_max = N - D - 1
		for i in range(0, group_starter_max + 1):
			group = arr[i:N:D]
			groups.append(group)
			group_avgs.append(sum(group) / len(group))
		if any((a != avg for a in group_avgs)):
			output.append(-1)
		else:
			num_steps = 0
			for group in groups:
				group = list((ele - avg for ele in group))
				nomod_sum = 0
				sum_of_mods = 0
				for k in range(0, len(group)):
					nomod_sum += group[k]
					sum_of_mods += abs(nomod_sum)
				num_steps += sum_of_mods
			output.append(int(num_steps))
for num in output:
	print(num)


test = int(input())
for z in range(test):
	counter = 0
	(N, D) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	l = len(arr)
	mean = 0
	num = 0
	for i in range(D):
		new_arr = [arr[j] for j in range(i, l, D)]
		s = sum(new_arr)
		leng = len(new_arr)
		if s % leng != 0:
			t = 0
			print('-1')
			break
		else:
			m = s // leng
			if i == 0:
				mean = m
			elif m != mean:
				t = 0
				print('-1')
				break
			for j in range(leng - 1):
				if new_arr[j] != mean:
					counter += abs(mean - new_arr[j])
					new_arr[j + 1] -= mean - new_arr[j]
					new_arr[j] = mean
				t = 1
	if t == 1:
		print(counter)


from collections import Counter
from functools import reduce
t = int(input())
while t:
	flag = 1
	(n, d) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ans = 0
	p = reduce(lambda x, y: x + y, l)
	p = p // n
	for i in range(0, d):
		j = i
		while j + d < n:
			if l[j] > p:
				l[j + d] += l[j] - p
				ans += l[j] - p
				l[j] = p
			elif l[j] < p:
				l[j + d] -= p - l[j]
				ans += p - l[j]
				l[j] = p
			j += d
	p = Counter(l)
	if len(p) > 1:
		flag = 0
	if flag == 1:
		print(ans)
	else:
		print('-1')
	t -= 1


for t in range(int(input())):
	(N, D) = map(int, input().split())
	a = list(map(int, input().split()))
	sum1 = 0
	ans = 0
	flag = 0
	for j in range(0, N):
		sum1 += a[j]
	avg = int(sum1 / N)
	for j in range(0, D):
		carry = a[j] - avg
		a[j] = avg
		k = j + D
		while k < N:
			a[k] += carry
			ans += abs(carry)
			carry = a[k] - avg
			a[k] = avg
			k = k + D
		if carry != 0:
			flag = 1
	for j in range(0, N):
		if a[j] != avg:
			flag = 1
	if flag == 1:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	su = sum(a)
	avg = su / n
	av = su // n
	flag = 0
	if avg != av:
		print(-1)
	else:
		c = 0
		a2 = [i - avg for i in a]
		for i in range(n - d):
			a2[i + d] += a2[i]
			c += abs(a2[i])
			a2[i] = 0
		f1 = 0
		for i in a2[-d:]:
			if i != 0:
				f1 = 1
				break
		if f1 == 0:
			print(int(c))
		else:
			print(-1)


def min(d, li, avg):
	count = 0
	for j in range(d):
		(fr, cur) = (0, 0)
		for k in range(len(li[j]) - 1):
			if cur == fr:
				if li[j][cur] < avg:
					sub = avg - li[j][cur]
					while sub != 0:
						fr += 1
						if sub - li[j][fr] > 0:
							count += li[j][fr] * (fr - cur)
							sub -= li[j][fr]
							li[j][fr] = 0
						else:
							count += sub * (fr - cur)
							li[j][fr] -= sub
							sub = 0
				else:
					sub = li[j][cur] - avg
					li[j][fr] = avg
					fr += 1
					li[j][fr] += sub
					count += sub
			else:
				sub = avg - li[j][cur]
				while sub != 0:
					if sub - li[j][fr] > 0:
						count += li[j][fr] * (fr - cur)
						sub -= li[j][fr]
						li[j][fr] = 0
						fr += 1
					else:
						count += sub * (fr - cur)
						li[j][fr] -= sub
						sub = 0
			cur += 1
	print(count)
t = int(input())
for i in range(t):
	inp = input().strip().split(' ')
	n = int(inp[0])
	d = int(inp[1])
	li = []
	for j in range(d):
		li.append([])
	j = 0
	sum = 0
	inp = input().strip().split(' ')
	while j < n:
		k = 0
		while k < d and j < n:
			sum += int(inp[j])
			li[k].append(int(inp[j]))
			j += 1
			k += 1
	avg = sum // n
	count = True
	if sum % n:
		print(-1)
	else:
		for j in range(d):
			sum = 0
			for k in li[j]:
				sum += k
				count += 1
			if sum % len(li[j]) or sum // len(li[j]) != avg:
				count = False
				break
		if count:
			min(d, li, avg)
		else:
			print(-1)


t = int(input())
i = 0
while i < t:
	(n, m) = input().strip().split(' ')
	n = int(n)
	m = int(m)
	li = [int(x) for x in input().strip().split(' ')]
	s = sum(li)
	val = int(s / n)
	if s % n == 0:
		count = 0
		j = 0
		while j + m < n:
			li[j + m] += li[j] - val
			count += abs(li[j] - val)
			j += 1
		while j < n:
			if li[j] != val:
				break
			j += 1
		if j < n:
			print(-1)
		else:
			print(count)
	else:
		print(-1)
	i += 1


t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	k = sum(li)
	c = 0
	if k % n == 0:
		x = k // n
		for i in range(0, len(li) - m):
			if li[i] < x:
				li[i + m] = li[i + m] - (x - li[i])
				c = c + (x - li[i])
				li[i] = x
			if li[i] > x:
				li[i + m] = li[i + m] + (li[i] - x)
				c = c + (li[i] - x)
				li[i] = x
		aa = 0
		for i in range(len(li)):
			if li[i] == li[0]:
				aa = aa + 1
		if aa == len(li):
			print(c)
		else:
			print('-1')
	else:
		print('-1')


t = int(input())
while t > 0:
	(n, d) = map(int, input().split(' '))
	done = d * [0]
	csum = n * [0]
	inp = list(map(int, input().split(' ')))
	s = sum(inp)
	if s % n == 0:
		k = s / n
		for (ind, i) in enumerate(inp):
			inp[ind] = i - k
		for i in range(0, d):
			prev = 0
			j = i
			while j < n:
				csum[j] = inp[j] + prev
				prev = csum[j]
				done[i] = csum[j]
				j += d
		flag = 1
		for check in done:
			if check != 0:
				flag = 0
				break
		if csum[-1] == 0 and flag:
			print(int(sum([abs(x) for x in csum])))
		else:
			print(-1)
	else:
		print(-1)
	t -= 1


t = int(input())
for test in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	suma = sum(a)
	if suma % n != 0:
		print(-1)
	else:
		final = suma // n
		moves = 0
		ptr1 = 0
		ptr2 = ptr1 + d
		while ptr1 < n and ptr2 < n:
			reqMoves = final - a[ptr1]
			a[ptr2] -= reqMoves
			moves += abs(reqMoves)
			ptr1 += 1
			ptr2 += 1
		while ptr1 < n:
			if a[ptr1] != final:
				moves = -1
				break
			ptr1 += 1
		print(moves)


import sys
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	num = list(map(int, input().split()))
	s = sum(num)
	if s % n != 0:
		print(-1)
		continue
	else:
		k = s // n
		ans = 0
		for i in range(n - p):
			ans += abs(num[i] - k)
			(num[i], num[i + p]) = (k, num[i] + num[i + p] - k)
		for i in num:
			if i != k:
				ans = -1
				break
		print(ans)


from math import *
T = int(input().strip())
for _ in range(T):
	(N, D) = input().strip().split(' ')
	(N, D) = [int(N), int(D)]
	A = list(map(int, input().strip().split(' ')))
	d = {k: [] for k in range(D)}
	flag = 0
	for j in range(N):
		d[j % D].append(A[j])
	for i in range(D - 1):
		if sum(d[i]) / len(d[i]) != sum(d[i + 1]) / len(d[i + 1]):
			flag = 1
			break
	if flag:
		print('-1')
	else:
		std_avg = sum(d[0]) / len(d[0])
		if ceil(std_avg) != floor(std_avg):
			print('-1')
		else:
			std_avg = sum(d[0]) // len(d[0])
			count = 0
			for i in range(D):
				loan = 0
				for j in range(len(d[i]) - 1):
					if d[i][j] != std_avg:
						loan = std_avg - d[i][j]
						count = count + abs(loan)
						d[i][j] = std_avg
						d[i][j + 1] = d[i][j + 1] - loan
			print(count)


def check(a, n, avg):
	for num in a:
		if num != avg:
			return False
	return True

def f(a, n, d):
	s = sum(a)
	avg = s / n
	if avg != s // n:
		return -1
	avg = int(avg)
	count = 0
	for i in range(n - d):
		count += abs(a[i] - avg)
		a[i + d] += a[i] - avg
		a[i] = avg
	if check(a, n, avg):
		return count
	return -1
for case in range(int(input())):
	(n, d) = tuple(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	print(f(a, n, d))


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	su = sum(l)
	h = 0
	fl = 0
	if su == su // x * x:
		s = su // x
		for i1 in range(x):
			if i1 - y >= 0 and l[i1 - y] > s:
				h += l[i1 - y] - s
				l[i1] = l[i1] + l[i1 - y] - s
				l[i1 - y] = s
			if l[i1] < s and i1 + y <= x - 1:
				h += s - l[i1]
				l[i1 + y] -= s - l[i1]
				l[i1] = s
		for i1 in range(x):
			if l[i1] != s:
				fl = 1
				break
	else:
		fl = 1
	if fl == 0:
		print(h)
	else:
		print(-1)


import sys
import math
t = int(input())
d = 0
n = 0
a = list()
for j in range(0, t):
	[n, d] = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	sum = 0
	for x in a:
		sum = sum + x
	if sum % n != 0:
		print(-1)
	else:
		avg = sum / n
		steps = 0
		for i in range(0, n - d):
			a[i + d] = a[i + d] + a[i] - avg
			steps = steps + abs(a[i] - avg)
			a[i] = avg
		flag = 1
		for i in range(n - d, n):
			if a[i] != avg:
				flag = 0
				break
		if flag == 0:
			print(-1)
		else:
			print(int(steps))


t = int(input())
for y in range(t):
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	a = [int(x) for x in input().split()]
	s = sum(a)
	if s % n == 0:
		s = s // n
		count = 0
		for i in range(n - d):
			if a[i] > s:
				count += a[i] - s
				a[i + d] += a[i] - s
				a[i] = s
			elif a[i] < s:
				count += s - a[i]
				a[i + d] -= s - a[i]
				a[i] = s
		c = 0
		for i in a:
			if i == s:
				c += 1
		if c == n:
			print(count)
		else:
			print(-1)
	else:
		print(-1)


n = int(input())
for k in range(0, n, 1):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in range(0, a[0], 1):
		s = s + b[i]
	t = s // a[0]
	flag = 0
	count = 0
	for i in range(0, a[1], 1):
		x = 0
		for j in range(i, a[0], a[1]):
			x = x + b[j]
		if x % t != 0:
			flag = 1
	if s % a[0] == 0 and flag == 0:
		for i in range(0, a[1], 1):
			for j in range(i, a[0], a[1]):
				if b[j] - t != 0 and j + a[1] <= a[0]:
					b[j + a[1]] = b[j + a[1]] + b[j] - t
					count = count + abs(b[j] - t)
		print(count)
	else:
		print('-1')


def solve(A, N, D):
	S = sum(A)
	if S % N != 0:
		return -1
	a_target = S // N
	count = 0
	i = 0
	i_max = N - D
	while i < i_max:
		diff = A[i] - a_target
		A[i + D] += diff
		count += abs(diff)
		i += 1
	while i < N:
		if A[i] != a_target:
			return -1
		i += 1
	return count
T = int(input())
for t in range(T):
	(N, D) = (int(i) for i in input().split())
	A = [int(i) for i in input().split()]
	print(solve(A, N, D))


def average(l):
	n = len(l)
	s = 0
	for i in l:
		s += i
	return s / n

def check_equal(l):
	n = len(l)
	for i in range(1, n):
		if l[i] != l[i - 1]:
			return False
	return True
t = int(input())
while t > 0:
	t -= 1
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	avg = average(l)
	ans = True
	if avg != int(avg):
		ans = False
	moves = 0
	if ans:
		avg = int(avg)
		for i in range(n):
			if i + d < n:
				if l[i] < avg:
					moves += avg - l[i]
					l[i + d] -= avg - l[i]
					l[i] = avg
				elif l[i] > avg:
					moves += l[i] - avg
					l[i + d] += l[i] - avg
					l[i] = avg
	if check_equal(l):
		print(moves)
	else:
		print(-1)


t = int(input())
lis2 = list()
for i in range(t):
	f = 0
	moves = 0
	(n, d) = map(int, input().split())
	lis = list(map(int, input().split()))
	if sum(lis) % n != 0:
		print('-1')
	else:
		a = sum(lis) // n
		for j in range(0, d, 1):
			s = 0
			p = 0
			lis2[:] = []
			if f == 0:
				for k in range(j, n, d):
					s = s + lis[k]
					p = p + 1
					lis2.append(lis[k])
				if s // p != a:
					print('-1')
					f = 1
					break
				else:
					st = 0
					for l in range(len(lis2) - 1):
						b = a - lis2[l]
						lis2[l] = lis2[l] + b
						lis2[l + 1] = lis2[l + 1] - b
						st = st + abs(b)
					moves = moves + st
		if f == 0:
			print(moves)
	lis[:] = []


for _ in range(int(input())):
	(n, d) = [int(e) for e in input().split(' ')]
	a = [int(e) for e in input().split(' ')]
	x = sum(a) / n
	if int(x) != x:
		print(-1)
	else:
		z = 0
		c = 0
		for i in range(n - d):
			y = a[i] + a[i + d]
			if y == 2 * x:
				z += abs(a[i] - a[i + d]) / 2
				a[i] = x
				a[i + d] = x
			else:
				z += abs(a[i] - x)
				a[i + d] += a[i] - x
				a[i] = x
		for i in range(n):
			if a[i] == x:
				c += 1
		if c == n:
			print(int(z))
		else:
			print(-1)


for _ in range(int(input())):
	(N, D) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr)
	avg = s // N
	steps = 0
	for i in range(N):
		if i + D < N:
			t = arr[i] - avg
			arr[i] = avg
			arr[i + D] += t
			steps += abs(t)
		elif arr[i] != avg:
			print(-1)
			break
	else:
		print(steps)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	avg = sum(a) / n
	cnt = 0
	if avg.is_integer() == True:
		for j in range(n - d):
			z = int(avg) - a[j]
			a[j] = avg
			a[j + d] -= z
			cnt += abs(z)
		if a.count(avg) == n:
			print(cnt)
		else:
			print(-1)
	else:
		print(-1)


t = int(input())
for i in range(0, t):
	nk = input()
	n = list(map(int, nk.split(' ')))
	ak = input()
	a = list(map(int, ak.split(' ')))
	num = 0
	for j in range(0, len(a)):
		num += a[j]
	sum1 = int(num / len(a))
	count = 0
	if num % len(a) == 0:
		for j in range(0, len(a) - n[1]):
			if a[j] < sum1:
				diff = sum1 - a[j]
				a[j + n[1]] = a[j + n[1]] - diff
				a[j] = a[j] + diff
				count += diff
			elif a[j] > sum1:
				diff = a[j] - sum1
				a[j + n[1]] = a[j + n[1]] + diff
				a[j] = a[j] - diff
				count += diff
		flag = 1
		for j in range(0, len(a)):
			if a[j] != sum1:
				flag = 0
				break
		if flag == 0:
			print(-1)
		else:
			print(count)
	else:
		print(-1)


test = int(input())
while test > 0:
	l1 = input()
	n_d = list(map(int, l1.split(' ')))
	n = n_d[0]
	d = n_d[1]
	l2 = input()
	arr = list(map(int, l2.split(' ')))
	sum1 = sum(arr)
	count = 0
	if sum1 % n == 0:
		avg = sum1 / n
		for i in range(0, n - d):
			if arr[i] > avg:
				count = count + (arr[i] - avg)
				arr[i + d] = arr[i + d] + (arr[i] - avg)
				arr[i] = arr[i] - (arr[i] - avg)
			elif arr[i] < avg:
				count = count + (avg - arr[i])
				arr[i + d] = arr[i + d] - (avg - arr[i])
				arr[i] = arr[i] + (avg - arr[i])
		flag = 0
		for i in range(n - d, n):
			if arr[i] != avg:
				flag = 1
				break
		if flag == 0:
			print(int(count))
		else:
			print('-1')
	else:
		print('-1')
	test = test - 1


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	tot = 0
	p = sum(l)
	if p % n != 0:
		print(-1)
		continue
	p /= n
	fin = [p] * n
	for i in range(n - d):
		if [i] == p:
			continue
		if l[i] > p:
			t = l[i] - p
			l[i] = p
			l[i + d] += t
		else:
			t = p - l[i]
			l[i] = p
			l[i + d] -= t
		tot += t
	if l == fin:
		print(int(tot))
	else:
		print(-1)


test = int(input())
for t in range(test):
	sw = input().split()
	(size, win) = (int(sw[0]), int(sw[1]))
	arr = [int(i) for i in input().split()]
	sum_arr = sum(arr)
	count = 0
	diff = 0
	fin = []
	if sum_arr % size != 0:
		print(-1)
	else:
		val = sum_arr // size
		for i in range(size):
			if i + win > size - 1:
				break
			l = arr[i]
			h = arr[i + win]
			if l == val:
				continue
			arr[i] = val
			if val < l:
				arr[i + win] = h + abs(val - l)
			else:
				arr[i + win] = h - abs(val - l)
			count += abs(val - l)
		if len(set(arr)) > 1:
			print(-1)
		else:
			print(count)


def equal(a, d):
	p = sum(a) // len(a)
	sm = 0
	ctr = 0
	cnt = 0
	for i in range(0, n - d):
		if a[i] < p:
			c = p - a[i]
			a[i] += c
			a[i + d] -= c
			sm += c
		elif a[i] > p:
			c = a[i] - p
			a[i + d] += c
			a[i] -= c
			sm += c
	if a.count(p) == len(a):
		ctr = 1
	if ctr:
		return sm
	else:
		return -1
t = int(input())
for a0 in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	if sum(a) % n != 0:
		print(-1)
	else:
		print(equal(a, d))


test = int(input())
for i in range(test):
	(N, D) = input().split()
	tab = list(map(int, input().split()))
	(num, u, N, D) = (0, 0, int(N), int(D))
	total = sum((x for x in tab))
	if total % N == 0:
		for step in range(D):
			sub = list(tab[step::D])
			totalsub = sum((x for x in sub))
			if totalsub % len(sub) == 0:
				value = int(totalsub / len(sub))
				if value == int(total / N):
					for val in range(len(sub) - 1):
						if sub[val] != value:
							(x, y) = (sub[val], sub[val + 1])
							if x < value:
								sub[val] = value
								num = num + (value - x)
								sub[val + 1] = y - (value - x)
							else:
								sub[val] = value
								sub[val + 1] = y + (x - value)
								num = num + (x - value)
				else:
					u = 1
					break
			else:
				u = 1
				break
		if u == 0:
			print(num)
		else:
			print(-1)
	else:
		print(-1)


for i in range(int(input())):
	sol = 0
	nd = list(map(int, input().split()))
	ai = list(map(int, input().split()))
	d = nd[1]
	if sol == -1:
		break
	for j in range(d):
		arr = ai[j::d]
		moy = sum(arr) / len(arr)
		if moy % 1 != 0:
			sol = -1
			break
		cpt = 0
		for l in range(len(arr) - 1):
			ecart = abs(moy - arr[l])
			if arr[l] < moy:
				cpt += ecart
				arr[l] += ecart
				arr[l + 1] -= ecart
			elif arr[l] > moy:
				cpt += ecart
				arr[l] -= ecart
				arr[l + 1] += ecart
		sol += cpt
	print(int(sol))


t = int(input().strip())
for a0 in range(t):
	(n, d) = input().strip().split()
	(n, d) = (int(n), int(d))
	a = [int(_) for _ in input().strip().split()]
	s = sum(a)
	if s % n != 0:
		print('-1')
		continue
	unit = s // n
	flag = 1
	ans = 0
	for i in range(d):
		j = i
		var = 0
		count = 0
		carry = 0
		while j < n:
			var += a[j]
			count += 1
			carry += a[j] - unit
			ans += abs(carry)
			j += d
		if var % count != 0 or var // count != unit:
			flag = 0
			break
	if flag == 0:
		print('-1')
	else:
		print(ans)


t = int(input())
for i in range(0, t):
	sum_ = 0
	ans = 0
	int_list = [int(x) for x in input().split()]
	n = int_list[0]
	k = int_list[1]
	input_num = [int(x) for x in input().split()]
	for i in input_num:
		sum_ = sum_ + i
	if sum_ % n != 0:
		print('-1')
		continue
	sum_ = sum_ / n
	for i in range(0, n):
		input_num[i] = input_num[i] - sum_
	for i in range(0, k):
		x = i
		h = 0
		while x < n:
			h = h + input_num[x]
			if x + k > n:
				break
			x = x + k
		if h:
			print('-1')
			break
	if h:
		continue
	for i in range(0, k):
		x = i
		while x < n:
			ans = ans + abs(input_num[x])
			if x + k >= n:
				break
			input_num[x + k] = input_num[x + k] + input_num[x]
			x = x + k
	print(int(ans))


sakura = int(input())
for sasuke in range(sakura):
	(kakashi, sharingan) = map(int, input().split())
	naruto = list(map(int, input().split()))
	hinata = sum(naruto)
	if hinata % kakashi != 0:
		print(-1)
		continue
	konohamaru = hinata / kakashi
	shikamaru = True
	hokage = 0
	for iruka in range(sharingan):
		orochimaru = 0
		rocklee = naruto[iruka:kakashi:sharingan]
		ino = sum(rocklee)
		choji = len(rocklee)
		if ino / choji != konohamaru:
			shikamaru = False
			break
		for gaara in rocklee[0:choji - 1]:
			orochimaru += gaara - konohamaru
			hokage += abs(orochimaru)
		if rocklee[choji - 1] + orochimaru != konohamaru:
			shikamaru = False
			break
	if not shikamaru:
		print(-1)
	else:
		print(int(hokage))


def solve(a, mid):
	low = high = 0
	ans = temp = t2 = 0
	for x in range(len(a)):
		if a[x] < mid:
			temp = mid - a[x]
			low += temp
		else:
			temp = mid - a[x]
			high -= temp
		t2 += temp
		ans += abs(t2)
	if low == high:
		return ans
	else:
		return -1
t = int(input())
while t:
	t -= 1
	(n, d) = map(int, input().split())
	ar = list(map(int, input().split()))
	ans = 0
	mv = sum(ar) // n
	for i in range(d):
		temp = [0] * (n // d + 1)
		j = i
		cnt = 0
		while j < n:
			temp[cnt] = ar[j]
			j += d
			cnt += 1
		if temp[-1] == 0:
			del temp[-1]
		t1 = solve(temp, mv)
		if t1 == -1:
			print(-1)
			break
		else:
			ans += t1
	else:
		print(ans)


for t in range(int(input())):
	(N, D) = map(int, input().split())
	A = list(map(int, input().split()))
	s = sum(A)
	if s % N == 0:
		x = s // N
		moves = 0
		for i in range(N - D):
			moves += abs(x - A[i])
			A[i + D] -= x - A[i]
		for i in range(N - D, N):
			if A[i] != x:
				moves = -1
				break
	else:
		moves = -1
	print(moves)


def solve(array):
	needs = []
	extra = []
	steps = 0
	for (index, value) in enumerate(array):
		if value < target:
			needs.append([index, target - value])
		elif value > target:
			extra.append([index, value - target])
		while needs and extra:
			to_take = min(needs[-1][1], extra[-1][1])
			needs[-1][1] -= to_take
			extra[-1][1] -= to_take
			steps += to_take * abs(needs[-1][0] - extra[-1][0])
			if needs[-1][1] == 0:
				needs.pop()
			if extra[-1][1] == 0:
				extra.pop()
	if needs or extra:
		return -1
	return steps
T = int(input())
for i in range(T):
	(n, D) = map(int, input().split())
	arrays = {x: [] for x in range(D)}
	total = 0
	for (index, element) in enumerate(map(int, input().split())):
		arrays[index % D].append(element)
		total += element
	if total % n != 0:
		print('-1')
		continue
	target = total // n
	moves = 0
	for x in arrays.values():
		m = solve(x)
		if m == -1:
			moves = -1
			break
		moves += m
	print(moves)


def all_same(items):
	return all((x == items[0] for x in items))
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	value = True
	list1 = list(map(int, input().split()))
	sum = 0
	for i in list1:
		sum += i
	avg = sum // len(list1)
	moves = 0
	for i in range(len(list1) - d):
		num = 0
		if list1[i] < avg:
			num = avg - list1[i]
			list1[i] += num
			list1[i + d] -= num
		elif list1[i] > avg:
			num = list1[i] - avg
			list1[i] -= num
			list1[i + d] += num
		moves += num
	if all_same(list1):
		print(moves, '\n')
	else:
		print('-1 \n')


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	count = 0
	sum = 0
	k = input()
	a = []
	a = [int(i) for i in k.split()]
	for i in a:
		sum = sum + i
	if n == 0:
		print(count)
		continue
	if sum % n != 0:
		print('-1')
		continue
	else:
		avg = int(sum / n)
		for i in range(n - d):
			if a[i] > avg:
				count += a[i] - avg
				a[i + d] += a[i] - avg
				a[i] = avg
			elif a[i] < avg:
				count += avg - a[i]
				a[i + d] -= avg - a[i]
				a[i] = avg
	for i in range(n):
		if a[i] != avg:
			count = -1
	print(count)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = [int(x) for x in input().split()]
	(s, c, count, flag) = (sum(a) // n, 0, 0, 1)
	for i in range(n - d):
		if a[i] >= s:
			c = a[i] - s
			a[i] -= c
			a[i + d] += c
		else:
			c = s - a[i]
			a[i] += c
			a[i + d] -= c
		count += c
	for i in range(n - d, n):
		if a[i] != s:
			flag = 0
			break
	if flag:
		print(count)
	else:
		print(-1)


T = int(input().strip())
while T:
	(N, D) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	s = sum(l)
	count = 0
	flag = True
	if s % N:
		flag = False
	else:
		eq = int(s / N)
		for i in range(len(l) - D):
			if l[i] > eq:
				count += abs(l[i] - eq)
				l[i + D] += abs(l[i] - eq)
				l[i] -= abs(l[i] - eq)
			elif l[i] != eq:
				count += abs(l[i] - eq)
				l[i + D] -= abs(l[i] - eq)
				l[i] += abs(l[i] - eq)
	for i in l:
		if i != eq:
			flag = False
	if flag:
		print(count)
	else:
		print(-1)
	T -= 1


t = int(input())
min_val = 1
while t:
	(n, m) = [int(i) for i in input().split()]
	values = [int(i) for i in input().split()]
	sum_val = sum(values)
	moves = 0
	if sum_val % n != 0:
		print(-1)
		t -= 1
		continue
	avg_val = int(sum_val / n)
	for i in range(n):
		if values[i] != avg_val:
			diff = values[i] - avg_val
			if i + m < n:
				values[i + m] += diff
				moves += abs(diff)
			elif values[i] != avg_val:
				print(-1)
				break
		if i == n - 1 and values[i] == avg_val:
			print(moves)
	t -= 1


def nMoves0(x, d):
	ret = 0
	neg = 0
	pos = 0
	for (i, y) in enumerate(x):
		if y < 0:
			pos = max(pos, i + 1)
			while pos < len(x):
				if x[pos] > 0:
					q = min(-y, x[pos])
					y += q
					x[pos] -= q
					ret += q * ((pos - i - 1) // d + 1)
					if y == 0:
						break
				pos += 1
		elif y > 0:
			neg = max(neg, i + 1)
			while neg < len(x):
				if x[neg] < 0:
					q = min(y, -x[neg])
					y -= q
					x[neg] += q
					ret += q * ((neg - i - 1) // d + 1)
					if y == 0:
						break
				neg += 1
	return ret

def nMoves(x, d):
	s = sum(x)
	if s % len(x) != 0:
		return -1
	ave = s // len(x)
	x = [y - ave for y in x]
	ret = 0
	for i in range(d):
		y = x[i::d]
		if sum(y) != 0:
			return -1
		ret += nMoves0(y, 1)
	return ret
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, d) = map(int, f.readline().split())
	x = list(map(int, f.readline().split()))
	print(nMoves(x, d))