It's John's birthday; he has brought some candies in distribute among N of his friends. Being a good friend, he decided to distribute all of his candies equally among his friend and he don't want to keep any for himself. He left the task of distributing candies up to his friends, but his friends haven't done a great job in distributing them and now they all have unequal amount of candies.
He asked all of his friends to keep all the candies in their hands (A[1] to A[N]) so that he can redistribute the candies. Taking a candy away from someone makes them sad and makes the person who gets it happy. Thus, you do not want to do many operations on the number of candies.
Here each operation stands for, taking away 1 candy from someone and giving it to somebody else.
After applying the operations, he might not be able to distribute all the candies among all of your friends, and you might need to buy some more candies as well. Buying each candy will be counted as 1 operation as well. John is saving up for his birthday party in the evening and so he wants to spend the least amount of money on candies as possible.
Thus, he asks for your help. You have to find the minimum number of operations required to make the distributions equal.

-----Input:-----
- The first line consists of the number T representing the number of test cases.
- Each test case consists of 2 lines.
- The first line contains of the number N representing the number of friends.
- The second line contains space separated numbers (A[1] to A[N]) representing the number of candies each friend currently has.

-----Output:-----
For each test case, you much print the minimum number of operations.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $0 \leq A[i] \leq 10^9$

-----Sample Input:-----
3

4

7 8 6 4

6

7 3 10 2 3 8

1

10   

-----Sample Output:-----
4

10

0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	div = sum(a) / n
	div = math.ceil(div)
	count = div * n - sum(a)
	for i in a:
		if i > div:
			count += i - div
	print(count)


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = math.ceil(sum(l) / n)
	ans = 0
	for i in l:
		x = m - i
		if x > 0:
			ans = ans + x
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	q = s // n
	r = s % n
	if r != 0:
		q += 1
	extra = 0
	k = []
	le = 0
	ans = 0
	for i in l:
		if i > q:
			extra += i - q
		elif i < q:
			ans += q - i
	print(ans)


for testcase in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	current_total = sum(values)
	equality_value = current_total / n
	if equality_value > int(equality_value):
		equality_value += 1
	equality_value = int(equality_value)
	deviations = list()
	net_deviations = 0
	for value in values:
		deviation = value - equality_value
		deviations.append(deviation)
		net_deviations += deviation
	minimum_operations = abs(net_deviations)
	for deviation in deviations:
		if deviation > 0:
			minimum_operations += deviation
	print(minimum_operations)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	if total % n != 0:
		new_total = int(n * (int(total / n) + 1))
	else:
		new_total = total
	cand = new_total // n
	op = new_total - total
	for j in a:
		if j > cand:
			op += j - cand
	print(op)


import math
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	v = math.ceil(sum(lst) / n)
	b = 0
	t = 0
	for i in lst:
		if i > v:
			b += i - v
	t += b
	for i in lst:
		if i < v:
			b -= v - i
			i += v - i
	t += abs(b)
	print(t)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	candies = sum(a)
	ans = 0
	r = candies % n
	d = candies // n
	if r == 0:
		ans = 0
	else:
		d = d + 1
		ans = n * d - candies
	for i in a:
		if i > d:
			ans += i - d
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	b = math.ceil(x / len(a))
	op = b * len(a) - x
	for i in range(len(a)):
		if a[i] >= b:
			op += a[i] - b
	print(op)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = sum(a) / n
	m = 0
	store = 0
	buy = 0
	if int(s) != s:
		s = int(s) + 1
	for i in a:
		if i < s:
			buy += s - i
		elif i > s:
			store += i - s
			m += i - s
	if store < buy:
		m += buy - store
	print(m)


import math
t = int(eval(input('')))
while t != 0:
	size = int(eval(input('')))
	a1 = input('').split()
	arr = []
	allcandies = 0
	for i in range(len(a1)):
		arr.append(int(a1[i]))
		allcandies += arr[i]
	candies = math.ceil(allcandies / size)
	ans = 0
	extra = 0
	for i in range(len(arr)):
		if arr[i] > candies:
			ans += arr[i] - candies
			extra += arr[i] - candies
		if arr[i] < candies:
			extra -= candies - arr[i]
	if extra < 0:
		ans += abs(extra)
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	can = list(map(int, input().split()))
	s = sum(can)
	if s % n == 0:
		dist = s // n
		op = 0
		for i in range(n):
			if can[i] > dist:
				op += can[i] - dist
		print(op)
	else:
		op = n - s % n
		dist = s // n + 1
		for i in range(n):
			if can[i] > dist:
				op += can[i] - dist
		print(op)


for _ in range(int(input())):
	N = int(input())
	l = [int(i) for i in input().split()]
	sum = 0
	for i in l:
		sum += i
	if sum % N == 0:
		avg = sum // N
	else:
		avg = sum // N + 1
	no_of_operations = avg * N - sum
	for i in l:
		if i > avg:
			no_of_operations += i - avg
		else:
			pass
	print(no_of_operations)


a = int(input())
z = []
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	p = 0
	if sum(c) % b != 0:
		p = p + b - sum(c) % b
		q = int(sum(c) / b) + 1
	else:
		q = int(sum(c) / b)
	for j in c:
		if j > q:
			p = p + j - q
	z.append(p)
for i in z:
	print(i)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		s = sum(arr)
		count = 0
		if s % n == 0:
			each = s // n
		else:
			each = s // n + 1
		for i in range(n):
			if arr[i] < each:
				count += each - arr[i]
		print(count)
except EOFError:
	pass