Read problems statements in Mandarin Chinese  and Russian. 

Grapes of Coderpur are very famous. Devu went to the market and saw that there were N people selling grapes. He didn’t like it because things were not very structured. So, he gave a task to Dhinwa to make things better. If Dhinwa successfully completes the task, Devu will be happy.

Devu wants to change the number of grapes in a bucket of zero or more sellers in such a way that the GCD  of all the number of grapes is divisible by K. Dhinwa can add or remove any number of grapes from each of the buckets. Adding or removing a grape will be counted as an operation. Also after the operation, none of the seller’s bucket should be empty.

Help Dhinwa in finding the minimum number of operations needed to make Devu happy. 
 
------ Input ------ 

First line of input contains an integer T denoting the number of test cases.  
For each test case, first line will contain an integer N denoting the number of buckets and integer K. 
Next line contains N space separated integers denoting the number of grapes in each of the bucket. 

------ Output ------ 

For each test case, print a single integer representing the answer of that test case.

------ Constraints ------ 

Subtask #1: 10 points

	$1 ≤ T  ≤ 10, 1 ≤ N ,K ≤ 10,  1 ≤ number of grapes in a bucket ≤ 10$

Subtask #2: 10 points

	$1 ≤ T  ≤ 10, 1 ≤ N,K  ≤ 100,  1 ≤ number of grapes in a bucket  ≤ 100$

Subtask #3: 80 points

	$1 ≤ T  ≤ 10, 1 ≤ N  ≤ 10^{5},  1 ≤ K ≤  10^{9},  1 number of grapes in a bucket ≤ 10^{9} $

----- Sample Input 1 ------ 
2

2 2

3 5

3 7

10 16 18
----- Sample Output 1 ------ 
2

8
----- explanation 1 ------ 

For the first test case, add or remove 1 grape in each of the bucket.

For the second test case, remove three grapes in the first bucket, remove two grapes from the second bucket and add three grapes in the third bucket.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
T = int(input())
for _ in range(0, T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in range(0, len(a)):
		if a[i] % k != 0:
			if a[i] < k:
				count += k - a[i]
			else:
				count += min(a[i] % k, k - a[i] % k)
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for x in l:
		if x < k:
			r = k - x
			c += r
		elif x % k != 0:
			r = x % k
			if r > int(k / 2):
				c = c + (k - r)
			else:
				c += r
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i <= b:
			c += b - i
		else:
			c += min(i % b, b - i % b)
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		x = i % k
		if i >= k:
			c += min(x, abs(k - x))
		else:
			c += k - x
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	count = 0
	for i in lis:
		if i < k:
			count += k - i
		else:
			count += min(i % k, k - i % k)
	print(count)


n = int(input())
for i in range(n):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	final = 0
	for i in l:
		r = i % k
		if i >= k:
			final = final + min(r, k - r)
		else:
			final += k - r
	print(final)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if l[i] >= k:
			r = l[i] % k
			m = min(r, k - r)
			c += m
		else:
			n = k - l[i]
			c += n
	print(c)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	cnt = 0
	for i in range(n):
		if arr[i] < k:
			cnt += k - arr[i]
		else:
			a = arr[i] // k
			b = abs(a * k - arr[i])
			c = abs((a + 1) * k - arr[i])
			cnt += min(b, c)
	print(cnt)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ams = 0
	m = 0
	for i in range(n):
		m = a[i] % k
		if a[i] < k:
			ams += k - a[i]
		else:
			ams += min(m, k - m)
	print(ams)


for _ in range(int(input())):
	(N, k) = map(int, input().split())
	B = list(map(int, input().split()))
	count = 0
	for i in range(N):
		r = B[i] % k
		if r != 0:
			if B[i] > k:
				count += min(r, k - r)
			else:
				count += k - r
	print(count)


x = int(input())
for i in range(0, x):
	[a, b] = [int(j) for j in input().split(' ')]
	s = [int(j) for j in input().split(' ')]
	p = 0
	for k in s:
		if k / b < 1:
			p = p + b - k % b
		else:
			p = p + min(k % b, b - k % b)
	print(p)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(len(l)):
		if l[i] < k:
			r = k - l[i]
			count = count + r
		else:
			r = l[i] % k
			s = k - r
			if s < r:
				m = s
			else:
				m = r
			count = count + m
	print(count)


for srn in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	c = 0
	for i in l:
		if i < k:
			c += k - i
		else:
			c += min(i % k, k - i % k)
	print(c)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		car = i % k
		if i - car == 0:
			car = k - car
		elif i - (k - car) == 0:
			car = car
		else:
			car = min(k - car, car)
		c += car
	print(c)


for _ in range(int(input())):
	(o, k) = map(int, input().split())
	z = list(map(int, input().split()))
	cnt = 0
	for i in z:
		if i < k:
			cnt = cnt + (k - i)
		else:
			q = i // k
			m = q * k
			n = (q + 1) * k
			cnt = cnt + min(abs(i - m), abs(i - n))
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	c = 0
	for i in li:
		r = i % k
		if i < k:
			c += k - i
		else:
			c += min(r, k - r)
	print(c)


T = int(input())

def algo():
	(N, K) = map(int, input().strip().split(' '))
	G = list(map(int, input().split(' ')))
	out = 0
	for i in G:
		if i <= K:
			out += K - i
		else:
			out += min(i % K, K - i % K)
	print(out)
for i in range(T):
	algo()


output = ''
for o in range(int(input())):
	nk = input()
	nk = nk.split()
	n = int(nk[0])
	k = int(nk[1])
	og = input().split()
	for i in range(n):
		og[i] = int(og[i])
	og.sort()
	oper = 0
	for j in range(n):
		if og[j] / k < 1:
			oper += k - og[j]
			og[j] = k
		elif og[j] % k <= k / 2:
			oper += og[j] % k
			og[j] -= og[j] % k
		else:
			oper += k - og[j] % k
			og[j] += k - og[j] % k
	og.sort()
	output += str(oper) + '\n'
print(output)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(n):
		rem = l[i] % k
		diff = k - rem
		if l[i] >= k:
			count += min(rem, diff)
		else:
			count += diff
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in a:
		t = i % k
		if i != 0:
			if i >= k:
				ans += min(t, k - t)
			else:
				ans += k - t
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	cnt = 0
	for i in l:
		if i % k == 0:
			continue
		elif i < k:
			cnt = cnt + k - i % k
		else:
			d = i // k
			cnt = cnt + min((d + 1) * k - i, i - d * k)
	print(cnt)


test_case = int(input())
for _ in range(test_case):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n):
		rem = arr[i] % k
		rem2 = k - rem
		if arr[i] >= k:
			count += min(rem, rem2)
		else:
			count += rem2
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in a:
		if i < k:
			ans += k - i
		else:
			j = i % k
			ans += min(j, k - j)
	print(ans)


for _ in range(int(input())):
	n = list(map(int, input().split()))
	m = list(map(int, input().split()))
	d = []
	for i in range(n[0]):
		k = m[i] // n[1]
		if k != 0:
			d.append(min(m[i] - k * n[1], (k + 1) * n[1] - m[i]))
		else:
			d.append(min((k + 1) * n[1] - m[i], (k + 1) * n[1] - m[i]))
	print(sum(d))


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		a = L[i] % k
		a1 = k - a
		if L[i] > a:
			ans += min(a, a1)
		else:
			ans += a1
	print(ans)


for _ in range(int(input())):
	(s, k) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	for i in l:
		t = i % k
		if i != 0:
			if i >= k:
				a += min(t, k - t)
			else:
				a += k - t
	print(a)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in a:
		r = i % k
		if i != 0:
			if i >= k:
				s += min(r, k - r)
			else:
				s += k - r
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for l in a:
		if l % k != 0:
			r = l % k
			if l < k:
				ans += k - r
			else:
				ans += min(r, k - r)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	op = 0
	for i in l:
		if i >= k:
			left = i % k
			right = k - left
			op += min(abs(left), abs(right))
		else:
			op += k - i
	print(op)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(n):
		r = l[i] // k
		a = (l[i] + k) // k
		new_r = l[i] - k * r
		new_a = k * a - l[i]
		if r != 0:
			count += min(new_r, new_a)
		else:
			count += new_a
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	res = 0
	for i in l1:
		t = i % k
		if i != 0:
			if i >= k:
				res += min(t, k - t)
			else:
				res += k - t
	print(res)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for j in arr:
		if j % k != 0:
			factor = j // k
			floor_ans = j - k * factor
			ceil_ans = k * (factor + 1) - j
			if factor == 0:
				ans += ceil_ans
			else:
				ans += min(floor_ans, ceil_ans)
	print(ans)


try:
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		res = 0
		for i in A:
			if i < K:
				res += K - i
				continue
			x = i % K
			res += min(x, K - x)
		print(res)
except:
	pass


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	g = list(map(int, input().split(' ')[:N]))
	count = 0
	for i in g:
		if i < K:
			count = count + (K - i)
		elif i == K:
			count += 0
		else:
			r = i % K
			nr = K - r
			if r < nr:
				count += r
			else:
				count += nr
	print(count)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	g = 0
	for i in a:
		if i < k:
			g += k - i
		else:
			r = i % k
			if k - i % k != 0:
				r = min(r, k - i % k)
			else:
				r = i % k
			g += r
	print(g)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in l:
		if i < k:
			count = count + (k - i)
		else:
			a = i % k
			b = k - a
			count = count + min(a, b)
	print(count)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	c = 0
	for i in s:
		h = i % k
		if i != 0:
			if i >= k:
				c += min(h, k - h)
			else:
				c += k - h
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	c = 0
	for i in range(n):
		r = l[i] % k
		if l[i] - r != 0 and r < k // 2 + 1:
			c += r
		else:
			c += k - r
	else:
		print(c)


t = int(input())
for ijn in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum1 = 0
	for i in a:
		if i < k:
			sum1 += k - i
		else:
			sum1 += min(i % k, k - i % k)
	print(sum1)


for t in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	N = [int(x) for x in input().split()]
	count = 0
	for n in N:
		if K > n:
			count += K - n
		else:
			count += min(n - int(n / K) * K, (int(n / K) + 1) * K - n)
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	c = 0
	for i in li:
		r1 = i % k
		if i < k:
			c += k - i
		else:
			q = i // k
			r2 = k * (q + 1) - i
			c += min(r1, r2)
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	c = 0
	for i in A:
		if i < k:
			c += k - i
		else:
			q = i % k
			c += min(q, k - q)
	print(c)


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	l = list(map(int, input().split()))
	b = 0
	for i in l:
		if i >= k:
			a = i // k
			b += min(abs(a * k - i), abs((a + 1) * k - i))
		else:
			b += abs(i - k)
	print(b)


import math
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	grapes = list(map(int, input().split()))
	ans = 0
	c = 0
	for g in grapes:
		if g % k == 0:
			c += 1
	if c == len(grapes):
		print(0)
	else:
		for g in grapes:
			if g % k == 0:
				continue
			else:
				floor = abs(g - g // k * k)
				if floor == g:
					floor = 2 ** 31
				ciel = abs(g - math.ceil(g / k) * k)
				ans += min(floor, ciel)
		print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		if i < b:
			mi = b - i
		else:
			mi = min(i % b, (i // b + 1) * b - i)
		s += mi
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		t = i % k
		if i != 0:
			if i >= k:
				c += min(t, k - t)
			else:
				c += k - t
	print(c)


T = int(input())
for tj in range(T):
	(N, K) = map(int, input().split())
	array_n = list(map(int, input().split()))
	count = 0
	for i in range(N):
		reminder = array_n[i] % K
		if reminder != 0:
			if array_n[i] < K:
				count += K - array_n[i]
			else:
				count += min(reminder, K - reminder)
	print(count)