Chefland is a $1D$ city where each of the $N$ houses is located at a distinct positive integer coordinate $A_{1}, A_{2}, \ldots A_{N}$. The chef is planning to create $K$ hills in the city. Note that two hills cannot be present at the same location but the location of hills and houses can overlap and each hill will also be at any integer (positive, negative or zero) coordinate. 

Each citizen would want to travel to the farthest hill from his house. Travelling will create air pollution and Chef wants to minimise the total pollution in the city. Help Chef find the minimum sum of distance travelled by everyone. In other words, help Chef create the hills at optimal locations, so that the sum of the distance of every house to the hill farthest from it is minimum possible.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains two lines of input.
First line contains $2$ integers $N, K$ separated by a space.
Second line contains $N$ integers $A_{1}, A_{2}, \ldots, A_{N}$, representing the location of the houses. 

------ Output: ------
For each testcase, find the minimum possible sum of distances if Chef creates the hills at optimal locations, in a separate line.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N, K ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$A_{i} < A_{i + 1} \forall$ valid $i$

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

3 1

1 2 3

1 5

1

2 2

1 5
----- Sample Output 1 ------ 
2

2

5
----- explanation 1 ------ 
TestCase 1: Optimal solution includes creating hill at $2$. Its distance from the house at coordinate $1$ is $1$, and so is its distance from the house at coordinate $3$. Its distance from the house at coordinate $2$ is $0$. Thus, total distance is $1+0+1=2$.

TestCase 2: Optimal solution includes creating hills at $\{-1, 0, 1, 2, 3 \}$. The farthest hills from the house at coordinate $1$ are at coordinates $-1$ and $3$. The citizen can choose to travel to any of them, and the distance shall be $2$.

TestCase 3: Optimal solution includes creating hills at $\{1, 2 \}$ or $\{4, 5 \}$.

Difficulty: VERY_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(min(sum([max(abs(arr[i] - (arr[n // 2] - k // 2)), abs(arr[i] - (arr[n // 2] + (k - 1) // 2))) for i in range(n)]), sum([max(abs(arr[i] - (arr[n // 2 - 1] - k // 2)), abs(arr[i] - (arr[n // 2 - 1] + (k - 1) // 2))) for i in range(n)])))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	s = 0
	if n % 2 == 0 and k % 2 == 0:
		for i in a:
			s += max(abs(i - (a[int(n / 2) - 1] - (k / 2 - 1))), abs(a[int(n / 2) - 1] + k / 2 - i))
		print(int(s))
	elif n % 2 == 0 and k % 2 != 0:
		for i in a:
			s += max(abs(i - (a[int(n / 2) - 1] - (k - 1) / 2)), abs(a[int(n / 2) - 1] + (k - 1) / 2 - i))
		print(int(s))
	elif n % 2 != 0 and k % 2 == 0:
		for i in a:
			s += max(abs(i - (a[int((n + 1) / 2) - 1] - (k / 2 - 1))), abs(a[int((n + 1) / 2) - 1] + k / 2 - i))
		print(int(s))
	else:
		for i in a:
			s += max(abs(i - (a[int((n + 1) / 2) - 1] - (k - 1) / 2)), abs(a[int((n + 1) / 2) - 1] + (k - 1) / 2 - i))
		print(int(s))


nn = int(input())
i = 0
ans = []
while i < nn:
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	b = [int(x) for x in input().split()]
	fit = b[n // 2] - k // 2
	sit = b[n // 2 - 1] - k // 2
	tr = [fit, sit]
	co = []
	for j in tr:
		lat = j + k - 1
		an = 0
		l = 0
		while l < n:
			q = max(abs(lat - b[l]), abs(j - b[l]))
			an = an + q
			l += 1
		co.append(an)
	ans.append(min(co))
	i += 1
for _ in ans:
	print(_)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	p = l[n // 2]
	hills = [i for i in range(p - math.floor(k / 2), p + math.ceil(k / 2))]
	s = 0
	for i in range(n):
		s += max(abs(hills[0] - l[i]), abs(hills[-1] - l[i]))
	print(s)


from sys import stdin

def solve():
	(n, k) = map(int, stdin.readline().split())
	lis = [*map(int, stdin.readline().split())]
	mid = lis[n // 2]
	final = 1e+18
	for kkk in range(2):
		if k % 2 == 0:
			low = k // 2 - 1
			hi = k // 2
		else:
			low = hi = k // 2
		if kkk == 1:
			(low, hi) = (hi, low)
		low = mid - low
		hi = mid + hi
		summ = 0
		for i in lis:
			summ += max(abs(low - i), abs(hi - i))
		final = min(final, summ)
	print(final)
t = int(stdin.readline())
while t:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	l = [int(x) for x in input().split(' ')]
	sum = 0
	if n % 2 == 0:
		sum = l[n // 2 - 1]
	else:
		sum = l[n // 2]
	ll = []
	ll.append(sum)
	i = 1
	while len(ll) < k:
		ll.append(sum - i)
		if len(ll) == k:
			break
		ll.append(sum + i)
		i += 1
	ll.sort()
	ans = 0
	for i in l:
		ans = ans + max(abs(i - ll[0]), abs(i - ll[-1]))
	if n % 2 == 0:
		sum = l[n // 2]
	else:
		sum = l[n // 2]
	ll = []
	ll.append(sum)
	i = 1
	while len(ll) < k:
		ll.append(sum - i)
		if len(ll) == k:
			break
		ll.append(sum + i)
		i += 1
	ll.sort()
	ans2 = 0
	for i in l:
		ans2 = ans2 + max(abs(i - ll[0]), abs(i - ll[-1]))
	print(min(ans, ans2))


from sys import stdin

def solve():
	(n, k) = map(int, stdin.readline().split())
	lis = [*map(int, stdin.readline().split())]
	mid = lis[n // 2]
	low = mid - k // 2
	hi = mid + k // 2
	if k % 2 == 0:
		hi -= 1
	summ = 0
	for i in lis:
		summ += max(abs(low - i), abs(hi - i))
	print(summ)
t = int(stdin.readline())
while t:
	solve()
	t -= 1


def find_distance(n, k, arr):
	start1 = arr[n // 2] - k // 2
	start2 = arr[n // 2 - 1] - k // 2
	ans = float('inf')
	for hill1 in [start1, start2]:
		hill2 = hill1 + k - 1
		dist = 0
		for house in arr:
			dist += max(abs(hill1 - house), abs(hill2 - house))
		ans = min(ans, dist)
	return ans
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(find_distance(n, k, arr))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = l[len(l) // 2]
	x = m
	y = m
	k -= 1
	while k > 0:
		k -= 1
		if k >= 0:
			x -= 1
		k -= 1
		if k >= 0:
			y += 1
	ans = 0
	for i in range(len(l)):
		ans += max(abs(y - l[i]), abs(l[i] - x))
	print(ans)


try:
	t = int(input())
	for i in range(t):
		(houses, hills) = input().split(' ')
		(houses, hills) = (int(houses), int(hills))
		lis = list(map(int, input().split(' ')))
		mid = lis[houses // 2]
		if houses % 2 != 0 and hills % 2 != 0:
			(up, low) = (mid, mid)
			for j in range(hills // 2):
				up += 1
				low -= 1
			print(sum([max(up - k, k - low) for k in lis]))
		elif houses % 2 != 0 and hills % 2 == 0:
			(up, low) = (mid, mid)
			for j in range(hills // 2 - 1):
				up += 1
				low -= 1
			if lis.count(up + 1) == 1:
				up += 1
			else:
				low -= 1
			print(sum([max(up - k, k - low) for k in lis]))
		elif houses % 2 == 0 and hills % 2 != 0:
			(up, low) = (mid, mid - 1)
			for j in range(hills // 2 - 1):
				up += 1
				low -= 1
			if lis.count(up + 1) == 1:
				up += 1
			else:
				low -= 1
			print(sum([max(up - k, k - low) for k in lis]))
		elif houses % 2 == 0 and hills % 2 == 0:
			(up, low) = (mid, mid - 1)
			for j in range(hills // 2 - 1):
				up += 1
				low -= 1
			print(sum([max(up - k, k - low) for k in lis]))
except:
	pass


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	min_sum = float('inf')
	if n == 1:
		return k // 2
	for mid in (a[(n - 1) // 2], a[(n - 1) // 2 + 1]):
		start = mid - (k - 1) // 2
		end = mid + k // 2
		dist_sum = 0
		for home in a:
			dist_sum += max(abs(home - start), abs(end - home))
		min_sum = min(min_sum, dist_sum)
	return min_sum
t = int(input())
for _ in range(t):
	print(solve())


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	h = A[math.ceil(n / 2) - 1]
	o = sum([abs(a - h) for a in A])
	print(o + (k - 1) // 2 * n + (0 if k % 2 else math.ceil(n / 2)))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	start = arr[int(n / 2) - 1] - int(k / 2)
	result = 100000000000000
	for j in range(start, start + 2):
		hill = j + k - 1
		result = min(sum([max(abs(hill - arr[x]), abs(j - arr[x])) for x in range(n)]), result)
	print(result)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = list(map(int, input().rstrip().split()))
	s1 = a[n // 2] - k // 2
	s2 = a[n // 2 - 1] - k // 2
	ans = 1e+18
	for h1 in [s1, s2]:
		h2 = h1 + k - 1
		d = 0
		for j in a:
			d += max(abs(h1 - j), abs(h2 - j))
		ans = min(ans, d)
	print(ans)


from sys import stdin, stdout
import sys

def get_ints():
	return map(int, stdin.readline().strip().split())

def get_list():
	return list(map(int, stdin.readline().strip().split()))

def get_string():
	return stdin.readline().strip()

def get_singleInt():
	return int(stdin.readline())

def main():
	testCases = get_singleInt()
	for i in range(testCases):
		(nHouses, kHills) = get_ints()
		housesArray = get_list()
		print(getMinDistance(housesArray, nHouses, kHills))

def getMinDistance(housesArray, nHouses, kHills):
	startingPoint1 = housesArray[nHouses // 2] - kHills // 2
	startingPoint2 = housesArray[nHouses // 2 - 1] - kHills // 2
	answer = sys.maxsize
	for point in [startingPoint1, startingPoint2]:
		endingPoint = point + kHills - 1
		distance = 0
		for house in housesArray:
			distance += max(abs(point - house), abs(endingPoint - house))
		answer = min(answer, distance)
	return answer
main()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))[:n]
	arr.sort()
	mid = arr[n // 2]
	for j in range(2):
		left_num = (k - 1) // 2
		right_num = k - 1 - left_num
		if j == 1:
			(left_num, right_num) = (right_num, left_num)
		left = mid - left_num
		right = mid + right_num
		ans = 0
		for j in range(n):
			ans += max(abs(arr[j] - left), abs(arr[j] - right))
	print(ans)


try:
	t = int(input())
	for i in range(0, t):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		med = a[n // 2]
		l = med - k // 2
		h = med + k // 2
		if k % 2 == 0:
			h -= 1
		count = 0
		for j in a:
			count += max(abs(j - l), abs(j - h))
		print(count)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mid = 0
	first = 0
	last = 0
	distance = 0
	if n % 2 == 1:
		mid = a[n // 2]
		first = mid - k // 2
		last = first + k - 1
	else:
		mid = a[n // 2 - 1] + (a[n // 2] - a[n // 2 - 1]) // 2
		if (a[n // 2] - a[n // 2 - 1]) % 2 == 0:
			first = mid - k // 2
			last = first + k - 1
		else:
			last = mid + k // 2
			first = last - k + 1
	for i in range(n):
		if a[i] <= first:
			distance += last - a[i]
		elif a[i] >= last:
			distance += a[i] - first
		else:
			distance += max(last - a[i], a[i] - first)
	print(distance)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = l[n // 2]
	a = m - k // 2
	h = m + k // 2
	if k % 2 == 0:
		h -= 1
	ans = 0
	for i in l:
		ans += max(abs(i - h), i - a)
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	k = n % 2
	if k == 0:
		k = n // 2 - 1
	else:
		k = n // 2
	(a, b) = (0, 0)
	if x % 2 == 1:
		x = x // 2
		a = l[k] - x
		b = l[k] + x
	else:
		x = x // 2
		a = l[k] - x + 1
		b = l[k] + x
	ans = 0
	for i in range(n):
		ans += max(abs(a - l[i]), b - l[i])
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = l[n // 2]
	left = m - k // 2
	right = left + k - 1
	count = 0
	for i in range(n):
		count += max(abs(left - l[i]), abs(l[i] - right))
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	fh = a[n // 2] - k // 2
	lh = fh + k - 1
	res = 0
	for val in a:
		res += max(abs(fh - val), abs(lh - val))
	print(res)


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	l = input().split()
	li = [int(i) for i in l]
	z = 0
	num1 = li[n // 2] - k // 2
	num2 = li[n // 2] + (k + 1) // 2 - 1
	for i in li:
		z += max(abs(i - num1), abs(i - num2))
	print(z)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	houses = list(map(int, input().split()))
	mid_hill = houses[(n - 1) // 2]
	(left, right) = (mid_hill - (k - 1) // 2, mid_hill + k // 2)
	print(sum(map(lambda x: max(x - left, right - x), houses)))


from math import ceil

def answer():
	median = a[n // 2]
	(f1, f2) = (median - ceil((k - 1) / 2), median + (k - 1) // 2)
	v = 0
	for i in a:
		v += max(abs(f1 - i), abs(f2 - i))
	return v
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(ii) for ii in input().split()]
	dd = sorted(a)
	cc = dd[n // 2] - k // 2
	if k % 2 == 0:
		cc = cc + 1
	cs = 0
	for ii in a:
		cs += max(abs(cc - ii), abs(cc + k - 1 - ii))
	cs2 = 0
	cc -= 1
	for ii in a:
		cs2 += max(abs(cc - ii), abs(cc + k - 1 - ii))
	cs3 = 0
	cc += 2
	for ii in a:
		cs3 += max(abs(cc - ii), abs(cc + k - 1 - ii))
	print(min(cs, cs2, cs3))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = a[n // 2] - k // 2
	ans = 0
	for i in range(n):
		left = m
		right = m + k - 1
		ans += max(abs(left - a[i]), abs(right - a[i]))
	print(ans)


import sys
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	left_hill1 = arr[n // 2] - k // 2
	left_hill2 = arr[n // 2 - 1] - k // 2
	ans = sys.maxsize
	for hill1 in [left_hill1, left_hill2]:
		hill2 = hill1 + k - 1
		distance = 0
		for house in arr:
			distance += max(abs(house - hill1), abs(house - hill2))
		ans = min(ans, distance)
	print(ans)


import sys
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	left_hill1 = arr[n // 2] - k // 2
	left_hill2 = arr[n // 2 - 1] - k // 2
	ans = sys.maxsize
	d1 = 0
	right_hill1 = left_hill1 + k - 1
	for house in arr:
		d1 += max(abs(house - left_hill1), abs(house - right_hill1))
	ans = min(ans, d1)
	d2 = 0
	right_hill2 = left_hill2 + k - 1
	for house in arr:
		d2 += max(abs(house - left_hill2), abs(house - right_hill2))
	ans = min(ans, d2)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	start1 = a[n // 2] - k // 2
	if n % 2 == 1:
		start2 = a[n // 2 - 1] - k // 2
	else:
		start2 = start1
	ans = float('inf')
	for hill1 in [start1, start2]:
		hill2 = hill1 + k - 1
		dist = 0
		for i in a:
			dist += max(abs(i - hill1), abs(i - hill2))
		ans = min(ans, dist)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	sm = sum(a)
	hills = []
	mid = a[n // 2]
	(i, j) = (mid - 1, mid)
	(lf, rt) = ([], [])
	prev = False
	(mn, mx) = (mid, mid)
	while k:
		if prev:
			mn = i
			i -= 1
			prev = False
		else:
			mx = j
			j += 1
			prev = True
		k -= 1
	ans = 0
	for x in a:
		ans += max(abs(mn - x), abs(mx - x))
	print(ans)


def answer(a, b):
	count = 0
	left = mid - a
	right = mid + b
	for i in range(0, len(A)):
		count = count + max(abs(A[i] - left), abs(A[i] - right))
	return count
t = int(input())
for _ in range(0, t):
	(n, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	mid = A[n // 2]
	if k % 2 != 0:
		a = (k - 1) // 2
		b = (k - 1) // 2
		print(answer(a, b))
	if k % 2 == 0:
		a = k // 2
		b = k // 2 - 1
		print(min(answer(a, b), answer(b, a)))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = l[n // 2]
	ans = [s]
	x = s
	k -= 1
	for i in range(k // 2):
		x -= 1
		ans.append(x)
	x = s
	for i in range((k + 1) // 2):
		x += 1
		ans.append(x)
	ans.sort()
	ans2 = [s]
	x = s
	for i in range((k + 1) // 2):
		x -= 1
		ans2.append(x)
	x = s
	for i in range(k // 2):
		x += 1
		ans2.append(x)
	ans2.sort()
	ans1e = 0
	ans2e = 0
	for i in range(n):
		ans1e += max(abs(l[i] - ans2[-1]), abs(l[i] - ans2[0]))
		ans2e += max(abs(l[i] - ans[-1]), abs(l[i] - ans[0]))
	ans3 = min(ans1e, ans2e)
	s = l[n // 2 - 1]
	ans = [s + 1]
	x = s + 1
	for i in range(k // 2):
		x -= 1
		ans.append(x)
	x = s + 1
	for i in range((k + 1) // 2):
		x += 1
		ans.append(x)
	ans.sort()
	ans2 = [s + 1]
	x = s + 1
	for i in range((k + 1) // 2):
		x -= 1
		ans2.append(x)
	x = s + 1
	for i in range(k // 2):
		x += 1
		ans2.append(x)
	ans2.sort()
	ans1e = 0
	ans2e = 0
	for i in range(n):
		ans1e += max(abs(l[i] - ans2[-1]), abs(l[i] - ans2[0]))
		ans2e += max(abs(l[i] - ans[-1]), abs(l[i] - ans[0]))
	print(min(ans3, ans1e, ans2e))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	arr = lis[:]
	arr.sort()
	med = arr[n // 2]
	c1 = len(arr[:n // 2])
	s1 = 0
	for i in arr[:n // 2]:
		s1 += med - i
	c2 = len(arr[n // 2 + 1:])
	s2 = 0
	for i in arr[n // 2 + 1:]:
		s2 += i - med
	ans = 0
	if k % 2 == 1:
		ans += s1 + k // 2 * c1
		ans += s2 + k // 2 * c2
		ans += k // 2
		print(ans)
	elif c1 > c2:
		ans += s1 + (k // 2 - 1) * c1
		ans += s2 + k // 2 * c2
		ans += k // 2
		print(ans)
	else:
		ans += s1 + k // 2 * c1
		ans += s2 + (k // 2 - 1) * c2
		ans += k // 2
		print(ans)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n % 2 == 0:
		med0 = a[n // 2 - 1]
		med1 = a[n // 2]
		r = abs(med1 - med0) + 1
		if k <= r:
			left = med0
			right = med0 + k - 1
			ans = 0
			for i in range(n):
				ans += max(abs(left - a[i]), abs(right - a[i]))
			print(ans)
		else:
			k -= r
			left = med0 - k // 2
			right = med1 + k // 2 + k % 2
			left1 = med0 - k // 2 - k % 2
			right1 = med1 + k // 2
			ans = 0
			ans1 = 0
			for i in range(n):
				ans += max(abs(left - a[i]), abs(right - a[i]))
				ans1 += max(abs(left1 - a[i]), abs(right1 - a[i]))
			print(min(ans, ans1))
	else:
		k -= 1
		med = a[n // 2]
		left = med - k // 2
		right = med + k // 2 + k % 2
		left1 = med - k // 2 - k % 2
		right1 = med + k // 2
		ans = 0
		ans1 = 0
		for i in range(n):
			ans += max(abs(left - a[i]), abs(right - a[i]))
			ans1 += max(abs(left1 - a[i]), abs(right1 - a[i]))
		print(min(ans, ans1))


def f1(n, k, lh):
	x = lh[len(lh) // 2]
	loc = [x]
	for i in range(1, k // 2 + 1):
		loc.append(x + i)
		loc.append(x - i)
	loc.sort()
	s = 0
	k1 = loc[0]
	k2 = loc[-1]
	kt = max(abs(x - loc[0]), abs(x - loc[1]))
	if n == 1:
		print(kt)
	elif n > 1 and k % 2 != 0:
		for i in lh:
			s += max(abs(k1 - i), abs(k2 - i))
		print(s)
	elif n > 1 and k % 2 == 0:
		loc.remove(loc[-1])
		k1 = loc[0]
		k2 = loc[-1]
		for i in lh:
			s += max(abs(k1 - i), abs(k2 - i))
		print(s)
import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lh = list(map(int, input().split()))
	s = 0
	if k == 1:
		x = lh[len(lh) // 2]
		for j in lh:
			s += abs(x - j)
		print(s)
	if k > 1:
		f1(n, k, lh)


def evaluate(arr, N, K):
	mountains = []
	if N % 2 == 0:
		midHouse = arr[N // 2 - 1]
	else:
		midHouse = arr[N // 2]
	mountains.append(midHouse)
	start = midHouse
	leftMost = midHouse
	rightMost = midHouse
	K -= 1
	i = 1
	while K > 0:
		mountains.append(start + i)
		rightMost = start + i
		K -= 1
		if K == 0:
			break
		mountains.append(start - i)
		leftMost = start - i
		K -= 1
		i += 1
	distance = 0
	for num in arr:
		if num <= midHouse:
			distance += rightMost - num
		else:
			distance += num - leftMost
	return distance
tc = int(input())
for i in range(tc):
	NK = [int(x) for x in input().split(' ')]
	N = NK[0]
	K = NK[1]
	arr = [int(x) for x in input().split(' ')]
	print(evaluate(arr, N, K))


def main():
	t = int(input())
	for _ in range(t):
		(n, k) = tuple(map(int, input().split()))
		A = list(map(int, input().split()))
		mid = A[(n - 1) // 2]
		dist = 0
		(a, b) = (mid - (k - 1) // 2, mid + (k - 1) // 2 + (1 - k % 2))
		for i in range(n):
			dist += max(A[i] - a, b - A[i])
		print(dist)
	return 0
main()


T = int(input())
for i in range(T):
	(N, K) = map(int, input().strip().split())
	houses = list(map(int, input().strip().split()))
	median_house = houses[N // 2]
	left_hill = median_house - K // 2
	right_hill = median_house + K // 2
	if K % 2 == 0:
		right_hill -= 1
	cost = 0
	for i in range(N):
		cost += max(abs(houses[i] - left_hill), abs(houses[i] - right_hill))
	print(cost)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = [int(i) for i in input().split()]
	A.sort()
	p = A[N // 2]
	l1 = [p]
	posi = p
	negi = p
	for i in range(K - 1):
		if i % 2:
			posi += 1
			l1.append(posi)
		else:
			negi -= 1
			l1.append(negi)
	s1 = 0
	l1.sort()
	for i in range(N):
		s1 += max(abs(A[i] - l1[0]), abs(A[i] - l1[-1]))
	print(s1)


t = int(input())
while t > 0:
	(n, k) = [int(ele) for ele in input().split()]
	arr = [int(ele) for ele in input().split()]
	ans = 0
	if n % 2 == 1:
		middle = (n - 1) // 2
		median = arr[middle]
		if k % 2 == 1:
			H1 = median - (k - 1) // 2
			H2 = median + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans += max
		else:
			ans1 = 0
			ans2 = 0
			H1 = median - k // 2
			H2 = median + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans1 += max
			H1 = median - (k - 1) // 2
			H2 = median + k // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans2 += max
			ans = min(ans2, ans1)
	else:
		median1 = arr[n // 2]
		median2 = arr[(n + 1) // 2]
		ans1 = 0
		ans2 = 0
		if k % 2 == 1:
			H1 = median1 - (k - 1) // 2
			H2 = median1 + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans1 += max
			H1 = median2 - (k - 1) // 2
			H2 = median2 + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans2 += max
			ans = min(ans1, ans2)
		else:
			ans11 = 0
			ans21 = 0
			H1 = median1 - k // 2
			H2 = median1 + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans11 += max
			H1 = median1 - (k - 1) // 2
			H2 = median1 + k // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans21 += max
			ans1 = min(ans21, ans11)
			ans12 = 0
			ans22 = 0
			H1 = median2 - k // 2
			H2 = median2 + (k - 1) // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans12 += max
			H1 = median2 - (k - 1) // 2
			H2 = median2 + k // 2
			for i in range(n):
				max = -2 ** 31
				if max < abs(H1 - arr[i]):
					max = abs(H1 - arr[i])
				if max < abs(H2 - arr[i]):
					max = abs(H2 - arr[i])
				ans22 += max
			ans2 = min(ans22, ans12)
			ans = min(ans1, ans2)
	print(ans)
	t -= 1


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	m = a[n // 2]
	ans1 = 0
	k -= 1
	k1 = m + k // 2 + k % 2
	k2 = m - k // 2
	for i in range(n // 2 + 1):
		ans1 += abs(a[i] - k1)
	for i in range(n // 2 + 1, n):
		ans1 += abs(a[i] - k2)
	ans2 = 0
	k1 = m + k // 2
	k2 = m - k // 2 - k % 2
	for i in range(n // 2):
		ans2 += abs(a[i] - k1)
	for i in range(n // 2, n):
		ans2 += abs(a[i] - k2)
	print(min(ans1, ans2))