You are given a number $n$ (divisible by $3$) and an array $a[1 \dots n]$. In one move, you can increase any of the array elements by one. Formally, you choose the index $i$ ($1 \le i \le n$) and replace $a_i$ with $a_i + 1$. You can choose the same index $i$ multiple times for different moves.

Let's denote by $c_0$, $c_1$ and $c_2$ the number of numbers from the array $a$ that have remainders $0$, $1$ and $2$ when divided by the number $3$, respectively. Let's say that the array $a$ has balanced remainders if $c_0$, $c_1$ and $c_2$ are equal.

For example, if $n = 6$ and $a = [0, 2, 5, 5, 4, 8]$, then the following sequence of moves is possible:

initially $c_0 = 1$, $c_1 = 1$ and $c_2 = 4$, these values are not equal to each other. Let's increase $a_3$, now the array $a = [0, 2, 6, 5, 4, 8]$;

$c_0 = 2$, $c_1 = 1$ and $c_2 = 3$, these values are not equal. Let's increase $a_6$, now the array $a = [0, 2, 6, 5, 4, 9]$;

$c_0 = 3$, $c_1 = 1$ and $c_2 = 2$, these values are not equal. Let's increase $a_1$, now the array $a = [1, 2, 6, 5, 4, 9]$;

$c_0 = 2$, $c_1 = 2$ and $c_2 = 2$, these values are equal to each other, which means that the array $a$ has balanced remainders.

Find the minimum number of moves needed to make the array $a$ have balanced remainders.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($3 \le n \le 3 \cdot 10^4$) — the length of the array $a$. It is guaranteed that the number $n$ is divisible by $3$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 100$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $150000$.


-----Output-----

For each test case, output one integer — the minimum number of moves that must be made for the $a$ array to make it have balanced remainders.


-----Examples-----

Input
4
6
0 2 5 5 4 8
6
2 0 2 1 0 0
9
7 1 3 4 2 10 3 9 6
6
0 1 2 3 4 5
Output
3
1
3
0


-----Note-----

The first test case is explained in the statements.

In the second test case, you need to make one move for $i=2$.

The third test case you need to make three moves:

the first move: $i=9$;

the second move: $i=9$;

the third move: $i=2$.

In the fourth test case, the values $c_0$, $c_1$ and $c_2$ initially equal to each other, so the array $a$ already has balanced remainders.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Mathematics

Constructive algorithms


Solutions:
import sys
import math

def fn(n, a):
	count = 0
	cnt = [0] * 3
	for i in range(n):
		cnt[a[i] % 3] = cnt[a[i] % 3] + 1
	if cnt[0] == cnt[1] == cnt[2]:
		return 0
	for i in range(3):
		m1 = max(cnt)
		j = cnt.index(m1)
		if m1 == n / 3:
			break
		if j == 2:
			cnt[0] = cnt[0] + m1 - n // 3
			cnt[2] = n // 3
			count = count + m1 - n // 3
		else:
			cnt[j] = n // 3
			cnt[j + 1] = cnt[j + 1] + m1 - n // 3
			count = count + m1 - n // 3
	return count
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[1 + l]
	a = data[l + 2:l + 2 + n]
	l = l + n + 1
	print(fn(n, a))


import sys
import math
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log
from bisect import bisect_right, bisect_left, bisect
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().rstrip().split()))
	r = n // 3
	for i in range(n):
		a[i] = a[i] % 3
	d = {0: 0, 1: 0, 2: 0}
	for i in range(n):
		d[a[i]] += 1
	ans = 0
	while not (d[0] == r and d[1] == r and (d[2] == r)):
		for i in d:
			if d[i] > r:
				val = d[i] - r
				d[i] = r
				d[(i + 1) % 3] += val
				ans += val
	print(ans)


import sys
from collections import defaultdict as dd
from collections import Counter as cc
from queue import Queue
import math
import itertools
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = lambda : sys.stdin.buffer.readline().rstrip()
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(c0, c1, c2) = (0, 0, 0)
	c = n // 3
	k = 0
	for i in range(n):
		if a[i] % 3 == 0:
			c0 += 1
		elif a[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	if c0 > c:
		l = c0 - c
		c0 = c
		k += l
		c1 += l
	if c1 > c:
		l = c1 - c
		c1 = c
		k += l
		c2 += l
	if c2 > c:
		l = c2 - c
		c2 = c
		k += l
		c0 += l
	if c0 > c:
		l = c0 - c
		c0 = c
		k += l
		c1 += l
	if c1 > c:
		l = c1 - c
		c1 = c
		k += l
		c2 += l
	if c2 > c:
		l = c2 - c
		c2 = c
		k += l
		c0 += l
	print(k)


import re
import sys
exit = sys.exit
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
d4 = [(0, -1), (-1, 0), (1, 0), (0, 1)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
t = ri()
for _ in range(t):
	n = ri()
	a = ris()
	goal = n // 3
	c = [0] * 3
	for x in a:
		c[x % 3] += 1
	ans = 0
	any = 1
	while any:
		any = 0
		for i in range(3):
			if c[i] > goal:
				d = c[i] - goal
				c[i] -= d
				c[(i + 1) % 3] += d
				ans += d
				any = 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r = []
	mov = 0
	for i in a:
		m = i % 3
		r.append(m)
	c0 = r.count(0)
	c1 = r.count(1)
	c2 = r.count(2)
	per = n // 3
	if c0 < per:
		while c0 < per:
			if c2 > per:
				mov = mov + 1
				c2 = c2 - 1
			else:
				mov = mov + 2
				c1 = c1 - 1
			c0 = c0 + 1
	if c1 < per:
		while c1 < per:
			if c0 > per:
				mov = mov + 1
				c0 = c0 - 1
			else:
				mov = mov + 2
				c2 = c2 - 1
			c1 = c1 + 1
	if c2 < per:
		while c2 < per:
			if c1 > per:
				mov = mov + 1
				c1 = c1 - 1
			else:
				mov = mov + 2
				c0 = c0 - 1
			c2 = c2 + 1
	print(mov)


def balanced_remainders():
	len_array = int(input())
	given_array = list(map(int, input().split()))
	stored_val = [0] * 3
	for i in given_array:
		stored_val[i % 3] += 1
	rem = len_array // 3
	min_num_moves = 0
	while stored_val[0] != rem or stored_val[1] != rem or stored_val[2] != rem:
		for i in range(3):
			if stored_val[i] >= rem:
				min_num_moves += stored_val[i] - rem
				stored_val[(i + 1) % 3] += stored_val[i] - rem
				stored_val[i] = rem
	return min_num_moves
number_of_testcases = int(input())
for _ in range(number_of_testcases):
	print(balanced_remainders())


import math
res = []
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	b = 0
	c = 0
	for i in l:
		i = i % 3
		if i == 0:
			a += 1
		elif i == 1:
			b += 1
		elif i == 2:
			c += 1
	co = 0
	n = (a + b + c) // 3
	while a != b or b != c or c != a:
		if a > n:
			b += a - n
			co += a - n
			a = n
		if b > n:
			c += b - n
			co += b - n
			b = n
		if c > n:
			a += c - n
			co += c - n
			c = n
	res.append(co)
for i in res:
	print(i)


t = int(input())
binary = [1 << i for i in range(32)]
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	c = [0, 0, 0]
	for i in a:
		c[i % 3] += 1
	target = n // 3
	cnt = 0
	if c[0] > target:
		cnt += c[0] - target
		c[1] += c[0] - target
		c[0] = target
	if c[1] > target:
		cnt += c[1] - target
		c[2] += c[1] - target
		c[1] = target
	if c[2] > target:
		cnt += c[2] - target
		c[0] += c[2] - target
		c[2] = target
	if c[0] > target:
		cnt += c[0] - target
		c[1] += c[0] - target
		c[0] = target
	print(cnt)


import sys

class BBalancedRemainders:

	def solve(self, tc=0):
		for _ in range(int(input())):
			n = int(input())
			a = [int(_) for _ in input().split()]
			ar = [x % 3 for x in a]
			c = [ar.count(0), ar.count(1), ar.count(2)]
			ans = 0
			d = n // 3
			mxi = c.index(max(c))
			for i in range(2):
				ans += max(0, c[mxi] - d)
				c[(mxi + 1) % 3] += max(0, c[mxi] - d)
				c[mxi] -= max(0, c[mxi] - d)
				mxi = (mxi + 1) % 3
				ans += max(0, c[mxi] - d)
				c[(mxi + 1) % 3] += max(0, c[mxi] - d)
				c[mxi] -= max(0, c[mxi] - d)
				mxi = (mxi + 1) % 3
				ans += max(0, c[mxi] - d)
				c[(mxi + 1) % 3] += max(0, c[mxi] - d)
				c[mxi] -= max(0, c[mxi] - d)
				mxi = (mxi + 1) % 3
			assert c == [d] * 3
			print(ans)
solver = BBalancedRemainders()
input = sys.stdin.readline
solver.solve()


t = int(input())
c = []
for i in range(t):
	n = input()
	a = input().split(' ')
	sum = 0
	a = list(map(int, a))
	for j in range(len(a)):
		a[j] = a[j] % 3
	x = a.count(0)
	y = a.count(1)
	z = a.count(2)
	pj = int((x + y + z) / 3)
	if x > pj:
		y += x - pj
		sum += x - pj
		x = pj
	if y > pj:
		z += y - pj
		sum += y - pj
		y = pj
	if z > pj:
		x += z - pj
		sum += z - pj
		z = pj
	if x > pj:
		y += x - pj
		sum += x - pj
		x = pj
	if y > pj:
		z += y - pj
		sum += y - pj
		y = pj
	c.append(sum)
for i in range(t):
	print(c[i])


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	three = [0, 0, 0]
	for i in num:
		if i % 3 == 0:
			three[0] += 1
		elif i % 3 == 1:
			three[1] += 1
		else:
			three[2] += 1
	res = 0
	while True:
		for i in range(3):
			if three[i] > n // 3:
				temp = three[i] - n // 3
				three[(i + 1) % 3] += temp
				res += temp
				three[i] -= temp
		switch = True
		if three[0] == three[1] and three[1] == three[2]:
			switch = False
		if not switch:
			break
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * 3
	ans = 0
	for i in range(n):
		x = a[i] % 3
		c[x] += 1
	if len(set(c)) == 1:
		print(0)
	else:
		x = n // 3
		if c[0] < x:
			y = x - c[0]
			if c[2] > x:
				y = min(y, c[2] - x)
				c[0] += y
				c[2] -= y
				ans += y
			if c[0] < x:
				y = x - c[0]
				if c[1] > x:
					y = min(y, c[1] - x)
					c[0] += y
					c[1] -= y
					ans += 2 * y
		if c[1] < x:
			y = x - c[1]
			if c[0] > x:
				y = min(c[0] - x, y)
				c[0] -= y
				c[1] += y
				ans += y
			if c[1] < x:
				y = x - c[1]
				if c[2] > x:
					y = min(y, c[2] - x)
					c[1] += y
					c[2] -= y
					ans += 2 * y
		if c[2] < x:
			y = x - c[2]
			if c[1] > x:
				y = min(c[1] - x, y)
				c[1] -= y
				c[2] += y
				ans += y
			if c[2] < x:
				y = x - c[2]
				if c[0] > x:
					y = min(y, c[0] - x)
					c[0] -= y
					c[2] += y
					ans += 2 * y
		print(ans)


import os
import sys
from io import BytesIO, IOBase

def solve(b, n):
	ans = 0
	for i in range(len(b)):
		if b[i] >= n // 3:
			ans = ans + b[i] - n // 3
			b[(i + 1) % 3] = b[(i + 1) % 3] + b[i] - n // 3
		else:
			ans = ans + (n // 3 - b[i])
			b[(i - 1) % 3] = b[(i - 1) % 3] - (n // 3 - b[i])
		b[i] = n // 3
	return ans

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = [0, 0, 0]
		for i in a:
			b[i % 3] += 1
		print(solve(b, n))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for i in [*open(0)][2::2]:
	q = [0] * 3
	for _ in map(int, i.split()):
		q[_ % 3] += 1
	print(max((q[i] - q[i - 1] for i in (0, 1, 2))))


import sys
from sys import stdin, stdout
from math import *
from collections import *
from itertools import *
int_arr = lambda : list(map(int, stdin.readline().strip().split()))

def solve(n, arr):
	req = n // 3
	(c, c0, c1, c2) = (0, 0, 0, 0)
	for i in range(len(arr)):
		if arr[i] % 3 == 0:
			c0 += 1
		elif arr[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	while c0 != req or c1 != req or c2 != req:
		if c0 <= req and c2 >= req:
			c0 += 1
			c2 -= 1
			c += 1
		elif c1 <= req and c0 >= req:
			c1 += 1
			c0 -= 1
			c += 1
		elif c2 <= req and c1 >= req:
			c2 += 1
			c1 -= 1
			c += 1
	print(c)
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = int_arr()
	solve(n, arr)


for s in [*open(0)][2::2]:
	c = [0] * 3
	for x in s.split():
		c[int(x) % 3] += 1
	print(max((c[i] - c[i - 1] for i in range(3))))


from math import log2, ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	c = [0, 0, 0]
	div = n // 3
	mat = [[0, 1, 2], [2, 0, 1], [1, 2, 0]]
	rel = [[1, 2], [2, 0], [0, 1]]
	rel2 = [[2, 1], [0, 2], [1, 0]]
	for i in range(n):
		c[a[i] % 3] += 1
	if c[0] == c[1] and c[1] == c[2]:
		print(0)
	else:
		taker = []
		giver = []
		for i in range(3):
			if c[i] < div:
				taker.append(i)
		for i in taker:
			while div - c[i] > 0:
				if c[rel2[i][0]] > div:
					excess = c[rel2[i][0]] - div
					minn = min(excess, div - c[i])
					ans += minn
					c[i] += minn
					c[rel2[i][0]] -= minn
				if c[i] < div:
					if c[rel2[i][1]] > div:
						excess = c[rel2[i][1]] - div
						minn = min(excess, div - c[i])
						ans += 2 * minn
						c[i] += minn
						c[rel2[i][1]] -= minn
		print(ans)


import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from math import gcd
MOD = int(1000000000.0 + 7)
INF = int(1e+20)
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
ii = lambda : int(input())
t = ii()
for _ in range(t):
	n = ii()
	arr = li()
	c0 = c1 = c2 = 0
	for i in arr:
		if i % 3 == 0:
			c0 += 1
		if i % 3 == 1:
			c1 += 1
		if i % 3 == 2:
			c2 += 1
	m = n // 3
	res = 0
	while True:
		if c0 == c1 == c2:
			break
		if c0 > m:
			res += c0 - m
			c1 += c0 - m
			c0 = m
		if c1 > m:
			res += c1 - m
			c2 += c1 - m
			c1 = m
		if c2 > m:
			res += c2 - m
			c0 += c2 - m
			c2 = m
	print(res)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = l[i] % 3
	a = l.count(0)
	b = l.count(1)
	c = l.count(2)
	ans = 0
	n //= 3
	if a > n:
		ans += a - n
		b += a - n
		a = n
	if a < n:
		ans += n - a
		c -= n - a
		a = n
	if b > n:
		ans += b - n
		c += b - n
		b = n
	if b < n:
		ans += n - b
		a -= n - b
		b = n
	if c > n:
		ans += c - n
		a += c - n
	if c < n:
		ans += n - c
		b -= n - c
	if a > n:
		ans += a - n
		b += a - n
	if a < n:
		ans += n - a
		c -= n - a
	if b > n:
		ans += b - n
		c += b - n
	if b < n:
		ans += n - b
		a -= n - b
	print(ans)


import math
test = int(input())

def getArr():
	return list(map(int, input().split()))

def get():
	return int(input())
while test > 0:
	n = get()
	arr = getArr()
	c0 = 0
	c1 = 0
	c2 = 0
	count = 0
	e = 0
	f = 0
	g = 0
	for p in arr:
		if p % 3 == 0:
			c0 += 1
		elif p % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	m = n // 3
	while c0 != m or c1 != m or c2 != m:
		if c0 > m:
			count += c0 - m
			c1 += c0 - m
			c0 -= c0 - m
		if c1 > m:
			count += c1 - m
			c2 += c1 - m
			c1 -= c1 - m
		if c2 > m:
			count += c2 - m
			c0 += c2 - m
			c2 -= c2 - m
	test -= 1
	print(count)


def balance(n, a):
	c0 = 0
	c1 = 0
	c2 = 0
	for i in a:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1

	def min(c):
		ind = 0
		for i in range(1, len(c)):
			if c[i] < c[ind]:
				ind = i
		return ind

	def max(c):
		ind = 0
		for i in range(1, len(c)):
			if c[i] > c[ind]:
				ind = i
		return ind
	c = [c0, c1, c2]
	if c0 == c1 and c1 == c2:
		ans = 0
	elif min(c) == (1 + max(c)) % 3:
		ans = c[max(c)] - n / 3
		s = c[min(c)] + c[max(c)] - 2 * n / 3
		if s < 0:
			ans += 2 * -1 * s
		else:
			ans += s
	else:
		ans = c[max(c)] - n / 3
		ans += n / 3 - c[min(c)]
	return int(ans)
t = int(input())
y = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	assert len(a) == n, 'Incorrect Input'
	y.append(a)
for a in y:
	print(balance(len(a), a))


n = int(input())
ans = []
for i in range(n):
	k = int(input())
	numlist = [int(num) % 3 for num in input().split()]
	comlist = [0, 0, 0]
	ave = k // 3
	for j in numlist:
		comlist[j] += 1
	comlist = [ave - num for num in comlist]
	jg = 0
	for j in comlist:
		if j > 0:
			jg += 1
	if jg == 1:
		index = comlist.index(max(comlist))
		comlist = comlist[index + 1:] + comlist[:index + 1]
	else:
		index = comlist.index(min(comlist))
		comlist = comlist[index:] + comlist[:index]
	sumnum = [comlist[0]]
	for j in range(1, 3):
		sumnum.append(sumnum[j - 1] + comlist[j])
	num = 0
	for j in sumnum:
		num += abs(j)
	ans.append(num)
for i in ans:
	print(i)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	c0 = 0
	c1 = 0
	c2 = 0
	for i in l:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	print(max(c2 - c1, c0 - c2, c1 - c0))


out = []
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c0, c2) = (0, 0, 0)
	c = [0] * 3
	for i in l:
		if i % 3 == 0:
			c[0] += 1
		elif i % 3 == 1:
			c[1] += 1
		else:
			c[2] += 1
	s = 0
	i = c.index(max(c))
	while c[i] != n // 3:
		x = c[i] - n // 3
		if i == 2:
			c[i] = n // 3
			c[0] += x
		else:
			c[i] = n // 3
			c[i + 1] += x
		s += x
		i = c.index(max(c))
	out.append(s)
for i in out:
	print(i)


import math
t = int(input())
for hh in range(0, t):
	n = int(input())
	a = [int(x) for x in input().split()]
	c0 = 0
	c1 = 0
	c2 = 0
	for i in range(0, n):
		if a[i] % 3 == 0:
			c0 += 1
		elif a[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	csame = n // 3
	ans = 0
	if c0 >= csame:
		xtra = c0 - csame
		c0 = csame
		ans += xtra
		c1 += xtra
	if c1 >= csame:
		xtra = c1 - csame
		c1 = csame
		ans += xtra
		c2 += xtra
	if c2 >= csame:
		xtra = c2 - csame
		c2 = csame
		ans += xtra
		c0 += xtra
	if c0 >= csame:
		xtra = c0 - csame
		c0 = csame
		ans += xtra
		c1 += xtra
	if c1 >= csame:
		xtra = c1 - csame
		c1 = csame
		ans += xtra
		c2 += xtra
	if c2 >= csame:
		xtra = c2 - csame
		c2 = csame
		ans += xtra
		c0 += xtra
	print(ans)


def solve(n, arr):
	d = [0, 0, 0]
	for i in arr:
		d[i % 3] += 1
	real = n // 3
	ans = 0
	while True:
		if d[0] == d[1] == d[2]:
			break
		for i in range(n):
			if d[arr[i] % 3] > real:
				d[arr[i] % 3] -= 1
				arr[i] += 1
				d[arr[i] % 3] += 1
				ans += 1
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


col = int(input())
for kk in range(col):
	a = input()
	n = list(map(lambda x: int(x), input().split()))
	c = [0, 0, 0]
	for i in n:
		c[i % 3] += 1
	avarage = sum(c) // 3
	counter = 0
	i = 0
	while c[0] != avarage or c[1] != avarage or c[2] != avarage:
		if c[-1] > avarage:
			c[-1] -= 1
			c[0] += 1
			counter += 1
		if c[0] > avarage:
			c[0] -= 1
			c[1] += 1
			counter += 1
		if c[1] > avarage:
			c[1] -= 1
			c[2] += 1
			counter += 1
	print(counter)


import sys
input = sys.stdin.readline

def read():
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	return (N, A)

def solve(N, A):
	ans = 10 ** 9
	C = [0, 0, 0]
	for a in A:
		C[a % 3] += 1
	target = N // 3
	if all([c == target for c in C]):
		return 0
	for i in range(3):
		(x, y, z) = (C[i % 3], C[(i + 1) % 3], C[(i + 2) % 3])
		a = 0
		d = max(target - z, 0)
		z += d
		y -= d
		a += d
		d = max(target - y, 0)
		y += d
		x -= d
		a += d
		if all([c == target for c in [x, y, z]]):
			ans = min(ans, a)
	return ans
T = int(input().strip())
for t in range(T):
	inputs = read()
	print('%s' % solve(*inputs))


t = int(input())
for test in range(t):
	(c0, c1, c2) = (0, 0, 0)
	n = int(input())
	a = list(map(int, input().split()))
	for i in a:
		if i % 3 == 0:
			c0 += 1
		if i % 3 == 1:
			c1 += 1
		if i % 3 == 2:
			c2 += 1
	cnt = 0
	while not c0 == c1 == c2:
		if c0 == max(c0, c1, c2):
			(c0, c1) = (c0 - 1, c1 + 1)
		elif c1 == max(c0, c1, c2):
			(c1, c2) = (c1 - 1, c2 + 1)
		elif c2 == max(c0, c1, c2):
			(c2, c0) = (c2 - 1, c0 + 1)
		cnt += 1
	print(cnt)


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	m = [0] * 3
	for num in arr:
		m[num % 3] += 1
	if m[0] == m[1] and m[1] == m[2]:
		return 0
	ideal_count = n // 3
	d = [0] * 3
	for (i, num) in enumerate(m):
		d[i] = num - ideal_count
	ans = 0
	for (i, num) in enumerate(d):
		if num >= 0:
			continue
		(prev_idx, prev_prev_idx) = ((i + 2) % 3, (i + 1) % 3)
		if d[prev_idx] <= 0:
			d[prev_prev_idx] += num
			d[i] = 0
			ans += num * -2
		elif abs(num) <= d[prev_idx]:
			d[prev_idx] += num
			d[i] = 0
			ans += -num
		else:
			ans += d[prev_idx]
			num += d[prev_idx]
			ans += num * -2
			d[prev_idx] = 0
			d[prev_prev_idx] += num
			d[i] = 0
	return ans
for _ in range(int(input())):
	print(solve())


import sys
from itertools import *
from math import *
from sys import stdin, stdout

def ans(n, lst):
	(c0, c1, c2) = (0, 0, 0)
	req = n // 3
	c = 0
	for i in lst:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		elif i % 3 == 2:
			c2 += 1
	while c0 != req or c1 != req or c2 != req:
		if c0 <= req and c2 >= req:
			c0 += 1
			c2 -= 1
			c += 1
		elif c1 <= req and c0 >= req:
			c1 += 1
			c0 -= 1
			c += 1
		elif c2 <= req and c1 >= req:
			c2 += 1
			c1 -= 1
			c += 1
	print(c)
for i in range(int(stdin.readline())):
	n = int(stdin.readline())
	lst = list(map(int, stdin.readline().split()))
	ans(n, lst)


from math import log

def ssolve(a):
	a = list(map(int, a.split()))
	c = [len([i for i in a if i % 3 == divisor]) for divisor in range(3)]
	cmax = len(a) / 3
	moves = 0
	for i in range(3):
		if c[i - 1] > cmax:
			moves += c[i - 1] - cmax
			c[i] += c[i - 1] - cmax
			c[i - 1] -= c[i - 1] - cmax
	return int(moves)

def solve(a):
	moves = 0
	a = list(map(int, a.split()))
	c0 = len([i for i in a if i % 3 == 0])
	c1 = len([i for i in a if i % 3 == 1])
	c2 = len([i for i in a if i % 3 == 2])
	cs = len(a) / 3
	c0 += c2 - cs if c2 > cs else 0
	moves += c0 - cs if c0 > cs else 0
	c1 += c0 - cs if c0 > cs else 0
	moves += c1 - cs if c1 > cs else 0
	c2 += c1 - cs if c1 > cs else 0
	moves += c2 - cs if c2 > cs else 0
	return int(moves)
t = int(input())
tests = []
for i in range(t):
	test_len = input()
	tests.append(input())
for i in tests:
	print(solve(i))

def test():
	assert solve('0 2 5 5 4 8') == 3
	assert solve('7 1 3 4 2 10 3 9 6') == 3


from sys import stdin, stdout

def INPUT():
	return list((int(i) for i in stdin.readline().split()))

def inp():
	return stdin.readline()

def out(x):
	return stdout.write(x)
from math import *
from decimal import *
INT_MAX = 10 ** 13
from bisect import bisect_left
import sys
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = INPUT()
	(c0, c1, c2) = (0, 0, 0)
	for i in range(n):
		if a[i] % 3 == 0:
			c0 += 1
		elif a[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	real = n // 3
	ans = 0
	m = max(c0, c1, c2)
	if c0 == c1 == c2:
		print(0)
		continue
	if c0 == m:
		ans += c0 - real
		c0 = real
		c1 += ans
		if c1 > real:
			ans += c1 - real
			print(ans)
			continue
		else:
			ans += 2 * (c2 - real)
			print(ans)
			continue
		continue
	if c1 == m:
		ans += c1 - real
		c1 = real
		c2 += ans
		if c2 > real:
			ans += c2 - real
			print(ans)
			continue
		else:
			ans += 2 * (c0 - real)
			print(ans)
			continue
		continue
	if c2 == m:
		ans += c2 - real
		c2 = real
		c0 += ans
		if c0 > real:
			ans += c0 - real
			print(ans)
			continue
		else:
			ans += 2 * (c1 - real)
			print(ans)
			continue
		continue


def getNoChangeToBalance(arr, n):
	count = 0
	cnt = [0] * 3
	for j in range(n):
		cnt[arr[j] % 3] += 1
	while min(cnt) != n // 3:
		for i in range(3):
			if cnt[i] > n // 3:
				count += 1
				cnt[i] -= 1
				cnt[(i + 1) % 3] += 1
	return count
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	res = getNoChangeToBalance(arr, n)
	print(res)
	t -= 1


import math

def mult_inp():
	return map(int, input().split(' '))

def inp():
	return list(map(int, input().split(' ')))

def binn(dp, it):
	left = 0
	right = len(dp)
	while left <= right:
		mid = (left + right) // 2
		if dp[mid] == it:
			return mid
		elif dp[mid] < it:
			left = mid + 1
		else:
			right = mid - 1
	return -1

def is_pow2(x):
	flag = [0] * 32
	for i in range(32):
		flag[i] = 2 ** i
	if x in flag:
		return True
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	a = inp()
	d = {0: 0, 1: 0, 2: 0}
	for i in a:
		d[i % 3] += 1
	mn = []
	for i in d:
		mn.append(d[i])
	if d[0] == d[1] and d[1] == d[2]:
		print(0)
		continue
	ans = 0
	while 1:
		if mn[1] == mn[2] and mn[2] == mn[0]:
			print(ans)
			break
		if min(mn) == mn[0]:
			res = n // 3 - mn[0]
			mn[2] -= res
			ans += res
			mn[0] = n // 3
		elif min(mn) == mn[1]:
			res = n // 3 - mn[1]
			mn[0] -= res
			ans += res
			mn[1] = n // 3
		elif min(mn) == mn[2]:
			res = n // 3 - mn[2]
			mn[1] -= res
			ans += res
			mn[2] = n // 3


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	r = [0, 0, 0]
	for i in range(n):
		r[a[i] % 3] += 1
	while r[0] != r[1] or r[1] != r[2]:
		c += 1
		k = r.index(max(r))
		r[k] -= 1
		r[(k + 1) % 3] += 1
	print(c)


t = int(input())
for _ in range(t):
	_ = input()
	data = list(map(int, input().split()))
	remainders = [0] * 3
	for element in data:
		remainders[element % 3] += 1
	counter = 0
	while not remainders[0] == remainders[1] == remainders[2]:
		max_ind = remainders.index(max(remainders))
		remainders[max_ind] -= 1
		remainders[(max_ind + 1) % 3] += 1
		counter += 1
	print(counter)


from math import log2 as lg
num = int(input())

def modify(a, b, length):
	ans = 0
	if a > length // 3:
		ans += a - length // 3
		b += a - length // 3
		a = length // 3
	return [a, b, ans]

def normalize(arr):
	ans = 0
	arr = list(map(lambda x: x % 3, arr))
	(n0, n1, n2) = (arr.count(0), arr.count(1), arr.count(2))
	(n2, n0, d1) = modify(n2, n0, len(arr))
	(n0, n1, d2) = modify(n0, n1, len(arr))
	(n1, n2, d3) = modify(n1, n2, len(arr))
	(n2, n0, d4) = modify(n2, n0, len(arr))
	(n0, n1, d5) = modify(n0, n1, len(arr))
	return d1 + d2 + d3 + d4 + d5
for it in range(num):
	n_el = int(input())
	mas = list(map(int, input().split()))
	print(normalize(mas))


import math
import sys
from collections import Counter
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a = [i % 3 for i in a]
	meow = Counter(a)
	meow[2] = meow.get(2, 0)
	meow[1] = meow.get(1, 0)
	meow[0] = meow.get(0, 0)
	target = meow.get(2, 0) + meow.get(1, 0) + meow.get(0, 0)
	target //= 3
	for i in range(3):
		meow[i] -= target
	ans = 0
	while meow[0] > 0:
		ans += 1
		meow[0] -= 1
		meow[1] += 1
	while meow[1] > 0:
		ans += 1
		meow[1] -= 1
		meow[2] += 1
	while meow[2] > 0:
		ans += 1
		meow[2] -= 1
		meow[0] += 1
	while meow[0] > 0:
		ans += 1
		meow[0] -= 1
		meow[1] += 1
	print(ans)


def solve(n, c):
	moves = 0
	while c[0] != c[1] or c[1] != c[2]:
		i = 0
		while c[i] <= n / 3:
			i += 1
		while c[i] > n / 3:
			c[i] -= 1
			c[(i + 1) % 3] += 1
			moves += 1
	return moves
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	c = [0 for _ in range(3)]
	for ai in a:
		c[ai % 3] += 1
	print(solve(n, c))


def main():
	T = input()
	for _ in range(int(T)):
		input()
		numbers = [int(x) for x in input().split()]
		remainder_counts = [0, 0, 0]
		for x in numbers:
			remainder_counts[x % 3] += 1
		target = len(numbers) // 3
		tot = 0
		while (x := move_max(remainder_counts, target)) != 0:
			tot += x
		print(tot)

def move_max(remainder_counts, target):
	m = remainder_counts[0]
	i = 0
	for j in [1, 2]:
		if remainder_counts[j] > m:
			m = remainder_counts[j]
			i = j
	remainder_counts[(i + 1) % 3] += m - target
	remainder_counts[i] = target
	return m - target
main()


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	nums = list(map(int, sys.stdin.readline().split()))
	div = [0, 0, 0]
	for i in nums:
		div[i % 3] += 1
	i = 0
	answer = 0
	while div[i] != n // 3 or div[(i + 1) % 3] != n // 3:
		x = max(0, div[i] - n // 3)
		div[i] -= x
		div[(i + 1) % 3] += x
		answer += x
		i = (i + 1) % 3
	print(answer)


t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	A = list(map(int, input().split()))
	A = [a % 3 for a in A]
	X = [A.count(i) - n // 3 for i in range(3)]
	for i in range(6):
		if X[i % 3] > 0:
			ans += X[i % 3]
			X[(i + 1) % 3] += X[i % 3]
			X[i % 3] = 0
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	rem = [0] * 3
	for i in a:
		rem[i % 3] += 1
	ans = 0
	for __ in range(2):
		for i in range(3):
			if rem[i] > n // 3:
				dec = rem[i] - n // 3
				rem[i] -= dec
				rem[(i + 1) % 3] += dec
				ans += dec
	print(ans)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = [0] * 3
	lol = []
	for x in arr:
		brr[x % 3] += 1
	if max(brr) == min(brr):
		print(0)
	else:
		print(max(brr[2] - brr[1], brr[0] - brr[2], brr[1] - brr[0]))


for tt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = [0] * 3
	for x in a:
		s[x % 3] += 1
	nd = n // 3
	ans = 0
	for it in range(30):
		for i in range(3):
			if s[i] > nd:
				ans += s[i] - nd
				s[(i + 1) % 3] += s[i] - nd
				s[i] = nd
	print(ans)


I = input
for _ in range(int(I())):
	n = int(I())
	c = [0] * 3
	for i in I().split():
		c[int(i) % 3] += 1
	print(max((c[i] - c[i - 1] for i in (0, 1, 2))))
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()


import collections
import math
from heapq import *
import bisect
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	out = 0
	k = [0, 0, 0]
	for i in nums:
		k[i % 3] += 1
	m = n // 3
	c = 0
	i = 0
	while c < 3:
		if k[i] == m:
			c += 1
		elif k[i] > m:
			out += k[i] - m
			k[(i + 1) % 3] += k[i] - m
			k[i] = m
		i = (i + 1) % 3
	print(out)


import sys

def main():
	input = sys.stdin.readline
	for _ in range(int(input())):
		(cnt, r) = ([int(input()) // -3] * 3, 0)
		for a in map(int, input().split()):
			cnt[a % 3] += 1
		for i in (0, 1, 2, 0):
			if cnt[i] > 0:
				r += cnt[i]
				cnt[i - 2] += cnt[i]
				cnt[i] = 0
		print(r)
main()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = c1 = c2 = 0
	for i in range(0, len(a)):
		if a[i] % 3 == 0:
			c0 += 1
		elif a[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	print(max(c0 - c2, c1 - c0, c2 - c1))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	c = [0, 0, 0]
	for i in a:
		c[i % 3] += 1
	n //= 3
	ans = 0
	for i in range(6):
		if c[i % 3] > n:
			c[(i + 1) % 3] += c[i % 3] - n
			ans += c[i % 3] - n
			c[i % 3] = n
	print(ans)


t = int(input())
arrays = []
for _ in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	arrays.append(array)

def compute_c(array):
	c = [0, 0, 0]
	for i in array:
		c[i % 3] += 1
	return c

def compute_k(c_array):
	target = sum(c_array) / 3
	count = 0
	while c_array != [target, target, target]:
		for (i, x) in enumerate(c_array):
			if x > target:
				c_array[i] = target
				c_array[(i + 1) % 3] += x - target
				count += x - target
	return int(count)
output = []
for array in arrays:
	c_array = compute_c(array)
	output.append(compute_k(c_array))
for x in output:
	print(x)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = n // 3
	d = []
	for i in range(n):
		d.append(l[i] % 3)
	a = d.count(0)
	b = d.count(1)
	c = d.count(2)
	s = 0
	if a - x > 0:
		s = s + (a - x)
		b = b + (a - x)
		a = x
	if b - x > 0:
		s = s + b - x
		c = c + b - x
		b = x
	if c - x > 0:
		s = s + c - x
		a = a + c - x
		c = x
	if a - x > 0:
		s = s + (a - x)
		b = b + (a - x)
		a = x
	print(s)


import sys
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
t = 1
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(c0, c1, c2) = (0, 0, 0)
	for el in a:
		if el % 3 == 0:
			c0 += 1
		elif el % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	needed = n // 3
	ans = 0
	while not (c1 == c2 and c1 == c0):
		if c0 > needed:
			c1 += c0 - needed
			ans += c0 - needed
			c0 = needed
		if c1 > needed:
			c2 += c1 - needed
			ans += c1 - needed
			c1 = needed
		if c2 > needed:
			c0 += c2 - needed
			ans += c2 - needed
			c2 = needed
	print(ans)


import sys
input = sys.stdin.readline
import math

def solution(n, arr):
	mod_ = 3
	count_mod = []
	avg_ = n // 3
	sol = 0
	c0 = len([1 for elem in arr if elem % mod_ == 0])
	c1 = len([1 for elem in arr if elem % mod_ == 1])
	c2 = len([1 for elem in arr if elem % mod_ == 2])
	count_mod = [c0, c1, c2]
	while max(count_mod) > avg_:
		for i in range(3):
			if count_mod[i] > avg_:
				move = count_mod[i] - avg_
				sol += move
				count_mod[i] -= move
				count_mod[(i + 1) % mod_] += move
	print(sol)
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	solution(n, arr)


for _ in range(0, int(input())):
	n = int(input())
	t = n // 3
	v = map(int, input().split())
	v = [x % 3 for x in v]
	c = [0, 0, 0]
	a = 0
	c[0] = v.count(0)
	c[1] = v.count(1)
	c[2] = v.count(2)
	for i in range(0, 3):
		d = t - c[i]
		if d > 0:
			x = min(max(c[(i + 2) % 3] - t, 0), d)
			a += x
			d -= x
			a += 2 * d
	print(a)


from collections import Counter
for _ in range(int(input())):
	input()
	d = Counter([int(x) % 3 for x in input().split()])
	print(max(d[0] - d[2], d[1] - d[0], d[2] - d[1]))


import sys
n = int(sys.stdin.readline())

def countNum(Arr):
	cNums = [0, 0, 0]
	cArrs = [[], [], []]
	cnt = 0
	for arr in Arr:
		if arr % 3 == 0:
			cNums[0] += 1
			cArrs[0].append(arr)
		elif arr % 3 == 1:
			cNums[1] += 1
			cArrs[1].append(arr)
		elif arr % 3 == 2:
			cNums[2] += 1
			cArrs[2].append(arr)
	while cNums[0] != cNums[1] or cNums[1] != cNums[2] or cNums[0] != cNums[2]:
		maxNumIdx = cNums.index(max(cNums))
		cNums[maxNumIdx] -= 1
		popNum = cArrs[maxNumIdx].pop()
		popNum += 1
		cArrs[popNum % 3].append(popNum)
		cNums[popNum % 3] += 1
		cnt += 1
	print(cnt)
for _ in range(n):
	m = int(sys.stdin.readline())
	Arr = list(map(int, sys.stdin.readline().split()))
	countNum(Arr)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(c, c1, c2, c3, b) = (0, 0, 0, 0, n // 3)
	for i in range(n):
		if a[i] % 3 == 1:
			c2 += 1
		elif a[i] % 3 == 2:
			c3 += 1
		else:
			c1 += 1
	while c1 != c2 or c2 != c3 or c1 != c3:
		if b < c1:
			c += c1 - b
			c2 += c1 - b
			c1 -= c1 - b
		if b < c2:
			c += c2 - b
			c3 += c2 - b
			c2 -= c2 - b
		if b < c3:
			c += c3 - b
			c1 += c3 - b
			c3 -= c3 - b
	print(c)


def main():
	for _ in range(int(input())):
		(n, r) = (int(input()) // 3, 0)
		cnt = [-n] * 3
		for a in map(int, input().split()):
			cnt[a % 3] += 1
		for i in (0, 1, 2, 0):
			if cnt[i] > 0:
				r += cnt[i]
				cnt[i - 2] += cnt[i]
				cnt[i] = 0
		print(r)
main()


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	x = 0
	y = 0
	z = 0
	for i in range(0, n):
		if arr[i] % 3 == 0:
			x = x + 1
		elif arr[i] % 3 == 1:
			y += 1
		else:
			z += 1
	ans = 0
	while 1:
		while y < n / 3:
			ans += 1
			y += 1
			x -= 1
		while z < n / 3:
			z += 1
			y -= 1
			ans = ans + 1
		while x < n / 3:
			x = x + 1
			z = z - 1
			ans = ans + 1
		if x == y and y == z:
			break
	t -= 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	third = n // 3
	c0 = 0
	c1 = 0
	c2 = 0
	for i in range(n):
		d = a[i] % 3
		if d == 0:
			c0 += 1
		elif d == 1:
			c1 += 1
		else:
			c2 += 1
	if c2 == c1 and c1 == c0:
		print(0)
	else:
		v = [c0, c1, c2]
		ans = 0
		d = third
		mx = max(v)
		ind = 0
		for i in range(3):
			if mx == v[i]:
				ind = i
		while 1:
			for i in range(3):
				if v[i] < d:
					r = d - v[i]
					pre = i - 1
					if pre == -1:
						pre = 2
					r = min(r, v[pre])
					v[pre] -= r
					v[i] += r
					ans += r
			if v[0] == v[1] == v[2]:
				break
		print(ans)


t = int(input())
b = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	(c0, c1, c2) = (0, 0, 0)
	for j in range(n):
		if a[j] % 3 == 0:
			c0 += 1
		elif a[j] % 3 == 1:
			c1 += 1
		else:
			c2 = c2 + 1
	b.append(max(c0 - c2, max(c2 - c1, c1 - c0)))
for i in range(len(b)):
	print(b[i])


from sys import stdin, stdout
it = lambda : int(stdin.readline())
st = lambda : stdin.readline().strip()
mp = lambda : map(int, stdin.readline().split())
lt = lambda : list(map(int, stdin.readline().split()))
ot = lambda s: stdout.write(str(s) + '\n')
test = it()
for _ in range(test):
	n = it()
	l = lt()
	r = [0, 0, 0]
	for x in range(n):
		if l[x] % 3 == 0:
			r[0] += 1
		elif l[x] % 3 == 1:
			r[1] += 1
		else:
			r[2] += 1
	(i, k, ff) = (0, 0, 0)
	n //= 3
	r = [x - n for x in r]
	while k < 3:
		if r[i] > 0:
			r[i % 3] -= 1
			r[(i + 1) % 3] += 1
			ff += 1
			k = 0
		else:
			k += 1
		i = (i + 1) % 3
	ot(ff)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * 3
	for i in a:
		b[i % 3] += 1
	if b[0] == b[1] == b[2]:
		print(0)
	else:
		print(max(b[1] - b[0], b[2] - b[1], b[0] - b[2]))


from math import log2
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ost = [0, 0, 0]
	for i in a:
		ost[i % 3] += 1
	need = sum(ost) // 3
	ans = 0
	if ost[2] > need:
		ans += ost[2] - need
		ost[0] += ost[2] - need
		ost[2] -= ost[2] - need
	if ost[0] > need:
		ans += ost[0] - need
		ost[1] += ost[0] - need
		ost[0] -= ost[0] - need
	if ost[1] > need:
		ans += ost[1] - need
		ost[2] += ost[1] - need
		ost[1] -= ost[1] - need
	if ost[2] > need:
		ans += ost[2] - need
		ost[0] += ost[2] - need
		ost[2] -= ost[2] - need
	if ost[0] > need:
		ans += ost[0] - need
		ost[1] += ost[0] - need
		ost[0] -= ost[0] - need
	if ost[1] > need:
		ans += ost[1] - need
		ost[2] += ost[1] - need
		ost[1] -= ost[1] - need
	print(ans)


for __ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	c0 = 0
	c1 = 0
	c2 = 0
	y = []
	for i in range(len(x)):
		if x[i] % 3 == 1:
			c1 += 1
		elif x[i] % 3 == 2:
			c2 += 1
		elif x[i] % 3 == 0:
			c0 += 1
	y.append(c0)
	y.append(c1)
	y.append(c2)
	if len(set(y)) == 1:
		print('0')
	elif len(set(y)) == 2:
		y = list(set(y))
		print(abs(y[0] - y[1]))
	else:
		c = 0
		i = 0
		kk = len(x) // 3
		while y[0] != kk or y[1] != kk or y[2] != kk:
			if y[i] > kk:
				y[i] -= 1
				if i + 1 == 3:
					y[0] += 1
				else:
					y[i + 1] += 1
				c += 1
			i += 1
			if i > 2:
				i = 0
		print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ar = [0, 0, 0]
	for i in range(n):
		ar[a[i] % 3] += 1
	ans = 0
	half = int(n / 3)
	if ar[0] > half:
		ans += ar[0] - half
		ar[1] += ar[0] - half
		ar[0] = half
	if ar[1] > half:
		ans += ar[1] - half
		ar[2] += ar[1] - half
		ar[1] = half
	if ar[2] > half:
		ans += ar[2] - half
		ar[0] += ar[2] - half
		ar[2] = half
	if ar[0] > half:
		ans += ar[0] - half
		ar[1] += ar[0] - half
		ar[0] = half
	print(ans)


from sys import stdin

def main():
	cases = int(stdin.readline().strip())
	while cases:
		n = int(stdin.readline().strip())
		v = [int(x) for x in stdin.readline().split()]
		div = [0, 0, 0]
		for i in range(n):
			div[v[i] % 3] += 1
		ans = 0
		aux = [0, 0, 0]
		i = 0
		r = n // 3
		while div[0] != div[1] or div[1] != div[2] or div[0] != div[2] or (sum(aux) != 0):
			if r < div[i]:
				aux[i] = div[i] - r
				div[i] = r
			if r > div[i]:
				for j in range(3):
					if aux[j] != 0:
						if aux[j] + div[i] <= r:
							if j < i:
								ans += abs(i - j) * aux[j]
							else:
								ans += abs(i + 3 - j) * aux[j]
							div[i] += aux[j]
							aux[j] = 0
						else:
							if j < i:
								ans += abs(i - j) * (aux[j] - (aux[j] + div[i] - r))
							else:
								ans += abs(i + 3 - j) * (aux[j] - (aux[j] + div[i] - r))
							aux[j] = aux[j] + div[i] - r
							div[i] = r
			i = (i + 1) % 3
		print(ans)
		cases -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c0 = c1 = c2 = 0
	base = n // 3
	ans = 0
	for i in range(n):
		if l[i] % 3 == 0:
			c0 += 1
		elif l[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	if c0 <= base and c1 <= base and (c2 >= base):
		ans += base - c0 + 2 * (base - c1)
	elif c1 <= base and c2 <= base and (c0 >= base):
		ans += base - c1 + 2 * (base - c2)
	elif c0 <= base and c2 <= base and (c1 >= base):
		ans += base - c2 + 2 * (base - c0)
	elif c0 <= base and c1 >= base and (c2 >= base):
		ans += 2 * (c1 - base) + (c2 - base)
	elif c1 <= base and c0 >= base and (c2 >= base):
		ans += 2 * (c2 - base) + (c0 - base)
	elif c2 <= base and c0 >= base and (c1 >= base):
		ans += 2 * (c0 - base) + (c1 - base)
	print(ans)


import sys
from typing import List
import random
import math

def offset_result(x: int) -> int:
	if x >= 0:
		return x + 1
	return -1

def load_input():
	whole_input = sys.stdin.readlines()
	t = int(whole_input[0])
	number_of_lines_per_test = 2
	tests = []
	for i in range(t):
		test_lines = []
		for y in range(number_of_lines_per_test):
			test_lines.append(whole_input[number_of_lines_per_test * i + y + 1].strip())
		n = int(test_lines[0])
		a = [int(x) for x in test_lines[1].split()]
		tests.append((n, a))
	return tests

def solve1(n: int, a: List[int]) -> int:
	answer = 0
	a = [x % 3 for x in a]
	c = [a.count(i) for i in range(3)]
	while c[0] != c[1] or c[1] != c[2]:
		diffs = [c[i] - c[(i + 1) % 3] for i in range(3)]
		max_diff = max(diffs)
		for i in range(3):
			if diffs[i] == max_diff:
				if max_diff == 1:
					subtract = 1
				else:
					subtract = diffs[i] // 2
				c[i] -= subtract
				c[(i + 1) % 3] += subtract
				answer += subtract
				break
	return answer
tests = load_input()
for x in tests:
	answer = solve1(*x)
	print(answer)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	a = n // 3
	x = y = z = 0
	for i in range(n):
		if l[i] % 3 == 0:
			x += 1
		elif l[i] % 3 == 1:
			y += 1
		else:
			z += 1
	print(max(x - z, y - x, z - y))


import sys
input = sys.stdin.readline

def inpit():
	return int(input())

def inplt():
	return list(map(int, input().split()))

def inpstr():
	s = input()
	return list(s[:len(s) - 1])

def inpspint():
	return map(int, input().split())
t = inpit()
for i in range(t):
	n = inpit()
	a = inplt()
	(c0, c1, c2) = (0, 0, 0)
	for i in a:
		if i % 3 == 0:
			c0 = c0 + 1
		if i % 3 == 1:
			c1 = c1 + 1
		if i % 3 == 2:
			c2 = c2 + 1
	m = 0
	while c0 != c2 or c1 != c0:
		if c0 > c1:
			m = m + 1
			c1 = c1 + 1
			c0 = c0 - 1
		if c1 > c2:
			m = m + 1
			c1 = c1 - 1
			c2 = c2 + 1
		if c2 > c0:
			m = m + 1
			c2 = c2 - 1
			c0 = c0 + 1
	print(m)


import sys

def int_inp():
	return int(sys.stdin.readline())
t = int_inp()
for _ in range(t):
	n = int_inp()
	l = list(map(int, sys.stdin.readline().strip().split()))
	(c0, c1, c2) = (0, 0, 0)
	count = 0
	for i in range(n):
		if l[i] % 3 == 0:
			c0 += 1
		elif l[i] % 3 == 1:
			c1 += 1
		elif l[i] % 3 == 2:
			c2 += 1
	x = n // 3
	count = 0
	if c0 > x:
		if c0 > x and c2 > x and (min(c0, c1, c2) == c1):
			count += c2 - x
			c2 -= count
			c0 += count
			a = (max(c0, c1) - min(c0, c1)) // 2
			count += a
			c0 -= a
			c1 += a
		else:
			count += c0 - x
			c0 -= count
			c1 += count
			a = (max(c1, c2) - min(c1, c2)) // 2
			count += a
			c1 -= a
			c2 += a
	if c1 > x:
		count += c1 - x
		c1 -= count
		c2 += count
		a = (max(c2, c0) - min(c2, c0)) // 2
		count += a
		c2 -= a
		c0 += a
	if c2 > x:
		count += c2 - x
		c2 -= count
		c0 += count
		a = (max(c0, c1) - min(c0, c1)) // 2
		count += a
		c0 -= a
		c1 += a
	print(count)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	(c0, c1, c2) = (-n // 3, -n // 3, -n // 3)
	w = list(map(int, input().split()))
	for i in w:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	print(max(0, c0) + max(0, c1 + max(0, c0)) + max(0, c2 + max(0, c1 + max(0, c0))) + max(0, c0 - max(0, c0) + max(0, c2 + max(0, c1 + max(0, c0)))))


t = int(input())
for o in range(0, t):
	s = 0
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	b = 0
	c = 0
	for i in l:
		if i % 3 == 0:
			a = a + 1
		elif i % 3 == 1:
			b = b + 1
		else:
			c = c + 1
	k = int(n / 3)
	if a < k:
		s = k - a
		c = c - s
		a = k
	else:
		s = a - k
		b = b + s
		a = k
	if b > c:
		s = s + b - k
	else:
		s = s + 2 * (c - k)
	print(s)


import operator
import os, sys
from collections import defaultdict, Counter, deque
from functools import lru_cache
from io import BytesIO, IOBase
from itertools import accumulate
from math import gcd, ceil, inf, sqrt, floor
import math

def main():
	for _ in range(0, int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		c0 = 0
		c1 = 0
		c2 = 0
		count = 0
		for i in arr:
			if i % 3 == 0:
				c0 += 1
			elif i % 3 == 1:
				c1 += 1
			else:
				c2 += 1
		if c0 == c1 == c2:
			print(0)
			continue
		while True:
			max1 = max(c0, c1, c2)
			if max1 == c0:
				c0 -= 1
				c1 += 1
				count += 1
			elif max1 == c1:
				c1 -= 1
				c2 += 1
				count += 1
			else:
				c2 -= 1
				c0 += 1
				count += 1
			if c0 == c1 == c2:
				break
		print(count)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	zoz = [int(x) for x in input().split()]
	rem = [0, 0, 0]
	poc = 0
	ind = 0
	for i in zoz:
		rem[i % 3] += 1
	while not (rem[0] == rem[1] and rem[1] == rem[2]):
		if max(rem[0], rem[1], rem[2]) == rem[0]:
			ind = 0
		elif max(rem[0], rem[1], rem[2]) == rem[1]:
			ind = 1
		else:
			ind = 2
		poc += rem[ind] - n // 3
		rem[(ind + 1) % 3] += rem[ind] - n // 3
		rem[ind] = n // 3
	res.append(poc)
for i in res:
	print(i)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	moves = 0
	(c0, c1, c2) = (0, 0, 0)
	for i in arr:
		if i % 3 == 0:
			c2 += 1
		elif i % 3 == 1:
			c0 += 1
		elif i % 3 == 2:
			c1 += 1
	print(max(c2 - c1, c1 - c0, c0 - c2))


mapping = {(0, 1): 1, (0, 2): 2, (1, 2): 1, (1, 0): 2, (2, 0): 1, (2, 1): 2}
t = int(input())
t_i = 0
while t_i < t:
	n = int(input())
	a = [int(i) for i in input().split()]
	c = [0, 0, 0]
	for a_i in a:
		c[a_i % 3] += 1
	cl = []
	for i in range(3):
		cl.append([c[i] - n // 3, i])
	cl = sorted(cl)
	r = 0
	while len(cl) > 1:
		value = mapping[cl[-1][1], cl[0][1]]
		if abs(cl[0][0]) > abs(cl[-1][0]):
			r += abs(cl[-1][0]) * value
			cl[0][0] += cl[-1][0]
			cl = cl[:-1]
		else:
			r += abs(cl[0][0]) * value
			cl[-1][0] += cl[0][0]
			cl = cl[1:]
	print(r)
	t_i += 1


t = int(input())
while t != 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	(zero, one, two) = (0, 0, 0)
	for i in range(n):
		if list1[i] % 3 == 0:
			zero += 1
		elif list1[i] % 3 == 1:
			one += 1
		else:
			two += 1
	ans = 0
	tar = n // 3
	c = 0
	for i in range(3):
		if zero > tar:
			one += zero - tar
			c += zero - tar
			zero = tar
		if one > tar:
			two += one - tar
			c += one - tar
			one = tar
		if two > tar:
			zero += two - tar
			c += two - tar
			two = tar
	print(c)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {0: 0, 1: 0, 2: 0}
	for i in arr:
		d[i % 3] = d.get(i % 3, 0) + 1
	ans = 0
	while d[0] != n // 3 or d[2] != n // 3 or d[1] != n // 3:
		if d[0] > n // 3:
			d[1] += d[0] - n // 3
			ans += d[0] - n // 3
			d[0] = n // 3
		if d[1] > n // 3:
			d[2] += d[1] - n // 3
			ans += d[1] - n // 3
			d[1] = n // 3
		if d[2] > n // 3:
			d[0] += d[2] - n // 3
			ans += d[2] - n // 3
			d[2] = n // 3
	print(ans)


def balancedRemainders(a):
	l = [0, 0, 0]
	n = len(a) // 3
	s = 0
	for i in a:
		l[i % 3] += 1
	for j in range(2):
		for i in range(3):
			if l[i] > n:
				s += l[i] - n
				l[(i + 1) % 3] += l[i] - n
				l[i] = n
	return s
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(balancedRemainders(a))


t = int(input())
x = []
c0 = 0
c1 = 0
c2 = 0
evenC = 0
result = 0
for i in range(t):
	x.append([int(input()), input().split(' ')])
for i in x:
	result = 0
	evenC = 0
	c0 = 0
	c1 = 0
	c2 = 0
	for j in i[1]:
		if int(j) % 3 == 0:
			c0 += 1
		elif int(j) % 3 == 1:
			c1 += 1
		elif int(j) % 3 == 2:
			c2 += 1
	evenC = (c0 + c1 + c2) / 3
	while c1 != evenC or c2 != evenC or c0 != evenC:
		if c0 > evenC:
			c1 += c0 - evenC
			result += c0 - evenC
			c0 -= c0 - evenC
		if c1 > evenC:
			c2 += c1 - evenC
			result += c1 - evenC
			c1 -= c1 - evenC
		if c2 > evenC:
			c0 += c2 - evenC
			result += c2 - evenC
			c2 -= c2 - evenC
	print(int(result))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	c = [0] * 3
	for el in a:
		c[el % 3] += 1
	if c[0] == c[1] == c[2]:
		print(0)
		continue
	c = [(c[i], i) for i in range(3)]
	d = {(0, 1): 1, (0, 2): 2, (1, 0): 2, (1, 2): 1, (2, 0): 1, (2, 1): 2}
	ans = 0
	for from_ in range(3):
		extra = c[from_][0] - n // 3
		if extra > 0:
			for to in {0, 1, 2} - {from_}:
				can = n // 3 - c[to][0]
				if can > 0:
					ans += d[c[from_][1], c[to][1]] * min(extra, can)
					extra -= can
	print(ans)


def cf_702B(numbers: list):
	n = len(numbers) // 3
	rem = {0: 0, 1: 0, 2: 0}
	extra = rem.copy()
	for num in numbers:
		rem[num % 3] += 1
	answer = 0
	for i in range(3):
		if rem[i] > n:
			extra[i] = rem[i] - n
			rem[i] = n
	while not rem[0] == rem[1] == rem[2]:
		for i in range(3):
			if extra[i]:
				rem[(i + 1) % 3] += extra[i]
				answer += extra[i]
				extra[i] = 0
				if rem[(i + 1) % 3] > n:
					extra[(i + 1) % 3] += rem[(i + 1) % 3] - n
					rem[(i + 1) % 3] = n
	return answer
for _ in range(int(input())):
	input()
	print(cf_702B(list(map(int, input().split()))))


T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	(C0, C1, C2) = (0, 0, 0)
	for j in range(N):
		if L[j] % 3 == 0:
			C0 += 1
		elif L[j] % 3 == 1:
			C1 += 1
		else:
			C2 += 1
	Equal = N // 3
	(E0, E1, E2) = (C0 - Equal, C1 - Equal, C2 - Equal)
	Moves = 0
	if C0 > Equal:
		Moves += E0
		E1 += E0
		C1 += E0
		E0 -= E0
	if C1 > Equal:
		Moves += E1
		E2 += E1
		C2 += E1
		E1 -= E1
	if C2 > Equal:
		Moves += E2
		E0 += E2
		C0 += E2
		E2 -= E2
	if C0 > Equal:
		Moves += E0
		E1 += E0
		C1 += E0
		E0 -= E0
	if C1 > Equal:
		Moves += E1
		E2 += E1
		C2 += E1
		E1 -= E1
	print(Moves)


t = int(input())
ans = ''
for i in range(t):
	c0 = 0
	c1 = 0
	c2 = 0
	n = int(input()) / 3
	a = list(map(int, input().split()))
	moves = 0
	for j in range(len(a)):
		if a[j] % 3 == 0:
			c0 += 1
		elif a[j] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	while c0 != n or c1 != n or c2 != n:
		if c0 > n:
			c1 += c0 - n
			moves += c0 - n
			c0 = n
		if c1 > n:
			c2 += c1 - n
			moves += c1 - n
			c1 = n
		if c2 > n:
			c0 += c2 - n
			moves += c2 - n
			c2 = n
	ans += str(int(moves)) + '\n'
print(ans)


answer_list = []
n = int(input())
for i in range(n):
	a = int(input())
	c0 = 0
	c1 = 0
	c2 = 0
	answer = 0
	list1 = list(map(int, input().split()))
	for x in list1:
		if x % 3 == 0:
			c0 += 1
		if x % 3 == 1:
			c1 += 1
		if x % 3 == 2:
			c2 += 1
	while c0 != c1 or c1 != c2 or c2 != c0:
		if c0 > c1:
			c0 -= 1
			c1 += 1
			answer += 1
		if c1 > c2:
			c1 -= 1
			c2 += 1
			answer += 1
		if c2 > c0:
			c2 -= 1
			c0 += 1
			answer += 1
	answer_list.append(answer)
for i in answer_list:
	print(i)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	A = [a % 3 for a in A]
	C = [A.count(i) for i in range(3)]
	ans = 0
	for j in range(3):
		while C[0] > N // 3:
			C[0] -= 1
			C[1] += 1
			ans += 1
		while C[1] > N // 3:
			C[1] -= 1
			C[2] += 1
			ans += 1
		while C[2] > N // 3:
			C[2] -= 1
			C[0] += 1
			ans += 1
	return ans
for _ in range(getInt()):
	print(solve())


import collections

def solveTestCase():
	n = int(input().split()[0])
	v = n / 3
	a = [int(i) for i in input().split()]
	vs = [0] * 3
	for i in a:
		vs[i % 3] += 1
	ret = 0
	for i in range(3):
		i_add = (i + 1) % 3
		to_add = v - vs[i_add]
		if to_add <= 0:
			continue
		can_add = vs[i] - v
		will_add = int(min(can_add, to_add))
		vs[i] -= will_add
		vs[i_add] += will_add
		ret += will_add
	for i in range(3):
		i_add = (i + 2) % 3
		to_add = v - vs[i_add]
		if to_add <= 0:
			continue
		can_add = vs[i] - v
		will_add = int(min(can_add, to_add))
		vs[i] -= will_add
		vs[i_add] += will_add
		ret += will_add * 2
	print(ret)
t = int(input().split()[0])
while t > 0:
	t -= 1
	solveTestCase()


t = int(input())
from collections import Counter

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	a = b = c = 0
	for i in l:
		if i % 3 == 0:
			a += 1
		elif i % 3 == 1:
			b += 1
		else:
			c += 1
	n = n // 3
	r = 0
	for i in range(2):
		if a > n:
			r += a - n
			b += a - n
			a = n
		if b > n:
			r += b - n
			c += b - n
			b = n
		if c > n:
			r += c - n
			a += c - n
			c = n
	return r
for i in range(t):
	print(solve())


import sys
it = iter(sys.stdin.read().splitlines())
t = int(next(it))
while t:
	n = int(next(it))
	m = [int(x) for x in next(it).split()]
	c = [0] * 3
	for i in m:
		c[i % 3] += 1
	(moves, carry) = (0, 0)
	for i in range(10):
		moves += carry
		c[i % 3] += carry
		carry = 0
		if c[i % 3] > n // 3:
			diff = c[i % 3] - n // 3
			carry += diff
			c[i % 3] -= diff
	print(moves)
	t -= 1


t = int(input())
for teste in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0, 0, 0]
	for k in a:
		b[k % 3] += 1
	m = n // 3
	s = 0
	for i in range(-3, 2):
		if b[i] > m:
			s += b[i] - m
			b[i + 1] += b[i] - m
			b[i] = m
	print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c0 = c1 = c2 = 0
	i = 0
	for i in l:
		a = i % 3
		if a == 0:
			c0 += 1
		elif a == 1:
			c1 += 1
		else:
			c2 += 1
	if c0 == n and c1 == n and (c3 == n):
		print('0')
		continue
	n = n // 3
	m = 0
	while c2 != n or c1 != n or c0 != n:
		if c2 > n:
			m += c2 - n
			c0 += c2 - n
			c2 = n
		if c1 > n:
			m += c1 - n
			c2 += c1 - n
			c1 = n
		if c0 > n:
			m += c0 - n
			c1 += c0 - n
			c0 = n
	print(m)


n = int(input())
a = []
for i in range(n):
	m = int(input())
	a.append(list(map(int, input().strip().split())))

def cyclist(v):
	v = v * 2
	g = v.index(max(v))
	output = v[g:g + 3]
	return output
for x in a:
	b = [0, 0, 0]
	for y in x:
		if y % 3 == 0:
			b[0] += 1
		if y % 3 == 1:
			b[1] += 1
		if y % 3 == 2:
			b[2] += 1
	b = cyclist(b)
	e = len(x) // 3
	if b[2] > e:
		b = [b[2], b[0], b[1]]
	print(2 * b[0] + b[1] - 3 * e)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = [0, 0, 0]
	ans = 0
	for i in a:
		if i % 3 == 0:
			x[0] += 1
		elif i % 3 == 1:
			x[1] += 1
		else:
			x[2] += 1
	while True:
		while x[0] < x[2]:
			x[0] += 1
			x[2] -= 1
			ans += 1
		if len(set(x)) == 1:
			break
		while x[1] < x[0]:
			x[1] += 1
			x[0] -= 1
			ans += 1
		if len(set(x)) == 1:
			break
		while x[2] < x[1]:
			x[2] += 1
			x[1] -= 1
			ans += 1
		if len(set(x)) == 1:
			break
	print(ans)


from collections import Counter, defaultdict
from math import factorial as fac
import bisect
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(int)
	for i in arr:
		d[i % 3] += 1
	ans = 0
	if d[0] > n // 3:
		d[1] += d[0] - n // 3
		ans += d[0] - n // 3
		d[0] = n // 3
	elif d[0] < n // 3:
		d[2] -= n // 3 - d[0]
		ans += n // 3 - d[0]
		d[0] = n // 3
	if d[1] > n // 3:
		d[2] += d[1] - n // 3
		ans += d[1] - n // 3
		d[1] = n // 3
	elif d[1] < n // 3:
		d[2] -= n // 3 - d[1]
		ans += (n // 3 - d[1]) * 2
		d[1] = n // 3
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	(c0, c1, c2) = (0, 0, 0)
	for i in arr:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		elif i % 3 == 2:
			c2 += 1
	avg = len(arr) / 3
	n = 0
	for _ in range(2):
		if c0 > avg:
			temp = c0 - avg
			c0 -= temp
			n += temp
			c1 += temp
		if c1 > avg:
			temp = c1 - avg
			c1 -= temp
			n += temp
			c2 += temp
		if c2 > avg:
			temp = c2 - avg
			c2 -= temp
			n += temp
			c0 += temp
	print(int(n))


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(200000)

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

def _p(x, end='\n'):
	stdout.write(str(x))
	stdout.write(end)
for t in range(int(_i())):
	n = int(_i())
	a = list(map(int, _i().split()))
	rem = [0, 0, 0]
	for num in a:
		rem[num % 3] += 1
	ans = 0
	for i in range(6):
		diff = rem[i % 3] - n // 3
		if diff > 0:
			rem[(i + 1) % 3] += diff
			rem[i % 3] = n // 3
			ans += diff
	_p(ans)
stdout.flush()


def balancedRemainder():
	n = int(input())
	count = [0, 0, 0]
	numsList = input().split()
	for i in numsList:
		num = int(i)
		count[num % 3] += 1
	move = 0
	target = int(len(numsList) / 3)
	for i in range(len(count)):
		if count[i] > target:
			amount = count[i] - target
			count[i] -= amount
			count[(i + 1) % 3] += amount
			move += amount
	if count[0] > target:
		amount = count[0] - target
		count[0] -= amount
		count[1] += amount
		move += amount
	print(move)
n = int(input())
for _ in range(n):
	balancedRemainder()


for _ in range(int(input())):
	n = int(input())
	lis = [int(x) for x in input().split()]
	c1 = 0
	c2 = 0
	c3 = 0
	ans = 0
	for val in lis:
		if val % 3 == 0:
			c1 += 1
		elif val % 3 == 1:
			c2 += 1
		else:
			c3 += 1
	while not (c1 == c2 and c2 == c3):
		ans += 1
		if c1 >= c2 and c1 >= c3:
			c1 -= 1
			c2 += 1
		elif c2 >= c1 and c2 >= c3:
			c2 -= 1
			c3 += 1
		else:
			c3 -= 1
			c1 += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = c1 = c2 = 0
	for i in a:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	x = n // 3
	ans = 0
	for i in range(2):
		if c0 > x:
			ans += c0 - x
			c1 += c0 - x
			c0 = x
		if c1 > x:
			ans += c1 - x
			c2 += c1 - x
			c1 = x
		if c2 > x:
			ans += c2 - x
			c0 += c2 - x
			c2 = x
	print(ans)


n = int(input())
for i in range(n):
	length = int(input())
	d = [-length / 3 for j in range(3)]
	arr = [int(j) for j in input().split()]
	for k in arr:
		if k % 3 == 0:
			d[0] += 1
		elif k % 3 == 1:
			d[1] += 1
		else:
			d[2] += 1
	if d[0] > 0 and d[1] > 0:
		print(int(2 * d[0] + d[1]))
	elif d[2] > 0 and d[1] > 0:
		print(int(2 * d[1] + d[2]))
	elif d[0] > 0 and d[2] > 0:
		print(int(2 * d[2] + d[0]))
	elif d[0] > 0:
		print(int(-d[1] + -2 * d[2]))
	elif d[1] > 0:
		print(int(-d[2] + -2 * d[0]))
	elif d[2] > 0:
		print(int(-d[0] + -2 * d[1]))
	else:
		print(0)


import os
import sys
import math
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def dijkstra(start, distance, path, n):
	visited = [False for _ in range(n)]
	distance[start] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not visited[v] and (v == -1 or distance[j] < distance[v]):
				v = j
		if distance[v] == math.inf:
			break
		visited[v] = True
		for edge in adj[v]:
			destination = edge[0]
			weight = edge[1]
			if distance[v] + weight < distance[destination]:
				distance[destination] = distance[v] + weight
				path[destination] = v

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 1
	while x * x <= n:
		if n % x == 0:
			if n // x == x:
				factors.append(x)
			else:
				factors.append(x)
				factors.append(n // x)
		x += 1
	return factors

def main():
	try:
		for _ in range(inp()):
			n = inp()
			a = inlt()
			(c0, c1, c2) = (0, 0, 0)
			ans = 0
			for i in range(n):
				if a[i] % 3 == 0:
					c0 += 1
				elif a[i] % 3 == 1:
					c1 += 1
				else:
					c2 += 1
			while True:
				if c0 == c1 == c2:
					print(ans)
					break
				elif c0 > n // 3:
					c1 += c0 - n // 3
					ans += c0 - n // 3
					c0 = n // 3
				elif c1 > n // 3:
					c2 += c1 - n // 3
					ans += c1 - n // 3
					c1 = n // 3
				elif c2 > n // 3:
					c0 += c2 - n // 3
					ans += c2 - n // 3
					c2 = n // 3
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
import sys
from collections import *

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

def cstr():
	return list(map(str, input().split(' ')))

def solve():
	n = int(input())
	lst = cint()
	czer = 0
	cone = 0
	ctwo = 0
	for i in range(n):
		lst[i] = lst[i] % 3
		if lst[i] == 0:
			czer += 1
		elif lst[i] == 1:
			cone += 1
		else:
			ctwo += 1
	avg = (czer + cone + ctwo) // 3
	ans = 0
	if czer == cone == ctwo:
		print(0)
	else:
		while not czer == cone == ctwo:
			if czer > avg:
				ans += czer - avg
				cone += czer - avg
				czer = avg
			elif czer < avg:
				ans += avg - czer
				ctwo -= avg - czer
				czer = avg
			if cone > avg:
				ans += cone - avg
				ctwo += cone - avg
				cone = avg
			elif cone < avg:
				ans += avg - cone
				czer -= avg - cone
				cone = avg
			if ctwo > avg:
				ans += ctwo - avg
				czer += ctwo - avg
				ctwo = avg
			elif ctwo < avg:
				ans += avg - ctwo
				cone -= avg - ctwo
				ctwo = avg
		print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	rems = defaultdict(int)
	size = n // 3
	for i in range(n):
		rems[arr[i] % 3] += 1
	ans = 0
	for k in range(0, 3):
		if rems[k] > size:
			rems[(k + 1) % 3] += rems[k] - size
			ans += rems[k] - size
			rems[k] = size
	num = [rems[0], rems[1], rems[2]]
	if num[0] > size and num[1] < size:
		ans += num[0] - size
	print(ans)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	R = []
	C1 = 0
	C2 = 0
	C3 = 0
	E = int(n // 3)
	for i in range(n):
		if L[i] % 3 == 0:
			C1 += 1
		if L[i] % 3 == 1:
			C2 += 1
		if L[i] % 3 == 2:
			C3 += 1
	C = [C1, C2, C3]
	M = max(C)
	Moves = 0
	while C[0] != E or C[1] != E or C[2] != E:
		for i in range(3):
			if C[i % 3] > E:
				Moves += C[i % 3] - E
				C[(i + 1) % 3] += C[i % 3] - E
				C[i % 3] = E
	print(Moves)


for _ in range(int(input())):
	n = int(input()) // 3
	arr = [-n] * 3
	for x in map(int, input().split()):
		arr[x % 3] += 1
	res = [0]

	def helper(i, j, x):
		if arr[i] < 0 and arr[j] > 0:
			delta = min(-arr[i], arr[j])
			arr[i] += delta
			arr[j] -= delta
			res[0] += x * delta
	helper(0, 2, 1)
	helper(1, 0, 1)
	helper(2, 1, 1)
	helper(0, 1, 2)
	helper(1, 2, 2)
	helper(2, 0, 2)
	print(res[0])


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		cnt = {0: 0, 1: 0, 2: 0}
		for v in a:
			cnt[v % 3] += 1
		(a, b, c) = (cnt[0], cnt[1], cnt[2])
		d = n // 3
		ans = 0
		for i in range(9):
			(a, b, c) = (c, a, b)
			if a > d:
				ans += a - d
				b += a - d
				a = d
		print(ans)
main()


get_line = lambda type_: list(map(type_, input().strip().split()))

def solve():
	n = int(input())
	goal = n // 3
	ops = 0
	a = get_line(int)
	c = [0, 0, 0]
	for a_i in a:
		c[a_i % 3] += 1
	while not c[0] == c[1] == c[2]:
		(big, small) = (0, 0)
		for i in range(3):
			if c[i] > c[big]:
				big = i
			if c[i] < c[small]:
				small = i
		if c[small] + (c[big] - goal) <= goal:
			ops += (small - big + 3) % 3 * (c[big] - goal)
			c[small] += c[big] - goal
			c[big] = goal
		else:
			ops += (small - big + 3) % 3 * (goal - c[small])
			c[big] -= goal - c[small]
			c[small] = goal
	print(ops)
t = int(input())
for _ in range(t):
	solve()


from math import floor
from collections import Counter

def fun(ls):
	lt = [i % 3 for i in ls]
	dct = Counter(lt)
	if dct.get(0) == None:
		dct[0] = 0
	if dct.get(1) == None:
		dct[1] = 0
	if dct.get(2) == None:
		dct[2] = 0
	c0 = dct.get(0)
	c1 = dct.get(1)
	c2 = dct.get(2)
	count = 0
	what_should_be = (c0 + c1 + c2) // 3
	while not c1 == c2 == c0:
		if c0 > c1:
			c0 = c0 - 1
			c1 = c1 + 1
			count += 1
			continue
		if c1 > c2:
			c1 = c1 - 1
			c2 = c2 + 1
			count += 1
			continue
		if c2 > c0:
			c2 = c2 - 1
			c0 = c0 + 1
			count += 1
	print(count)
T = int(input())
for i in range(T):
	t = int(input())
	ls = list(map(int, input().split()))
	fun(ls)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	w = [0] * 3
	for i in list(map(int, input().split())):
		w[i % 3] += 1
	print(max((w[i] - w[i - 1] for i in range(3))))


def balancedRemainders(n, arr):
	c0 = 0
	c1 = 0
	c2 = 0
	for i in range(0, n):
		if arr[i] % 3 == 0:
			c0 += 1
		elif arr[i] % 3 == 1:
			c1 += 1
		elif arr[i] % 3 == 2:
			c2 += 1
	limit = int(n / 3)
	moves = 0
	for i in range(0, 2):
		if c0 > limit:
			moves += c0 - limit
			c1 += c0 - limit
			c0 = limit
		if c1 > limit:
			moves += c1 - limit
			c2 += c1 - limit
			c1 = limit
		if c2 > limit:
			moves += c2 - limit
			c0 += c2 - limit
			c2 = limit
	print(moves)
	return
tc = int(input())
for _ in range(0, tc):
	n = int(input())
	arr = [int(i) for i in input().split()][:n]
	balancedRemainders(n, arr)


def arr_to_c(array):
	res = [0] * 3
	for elem in array:
		res[elem % 3] += 1
	return res

def stabilize(numbers, value):
	res = 0
	if numbers[0] > value:
		move = numbers[0] - value
		numbers[0] -= move
		numbers[1] += move
		res += move
	if numbers[1] > value:
		move = numbers[1] - value
		numbers[1] -= move
		numbers[2] += move
		res += move
	if numbers[2] > value:
		move = numbers[2] - value
		numbers[2] -= move
		numbers[0] += move
		res += move
	if numbers[0] > value:
		move = numbers[0] - value
		numbers[0] -= move
		numbers[1] += move
		res += move
	return res
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	numbers = arr_to_c(array)
	value = n // 3
	print(stabilize(numbers, value))


t = int(input())
for _ in range(t):
	n = int(input())
	balance = n // 3
	array = list(map(int, input().split()))
	c = [0, 0, 0]
	for a in array:
		c[a % 3] += 1
	ans = 0
	if c[0] >= balance:
		ans += c[0] - balance
		if c[1] + c[0] - balance >= balance:
			ans += c[1] + c[0] - balance - balance
		else:
			ans += 2 * (c[2] - balance)
	elif c[1] >= balance:
		ans += 2 * (c[1] - balance) + c[2] - balance
	elif c[2] >= balance:
		ans += 2 * (c[2] - balance) + c[0] - balance
	print(ans)


import sys

def solve(n, a):
	res = 0
	c = [0] * 3
	for x in a:
		c[x % 3] += 1
	for i in range(6):
		if c[i % 3] >= n // 3:
			d = c[i % 3] - n // 3
			c[i % 3] -= d
			c[(i + 1) % 3] += d
			res += d
	return res

def main():
	res = ''
	input = sys.stdin.readline
	print = sys.stdout.write
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		res += str(solve(n, a)) + '\n'
	print(res)
main()


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	rem = [0] * 3
	for i in lis:
		rem[i % 3] += 1
	a = n // 3
	ans = max(rem) - a
	aa = rem[(rem.index(max(rem)) + 1) % 3] + ans - a
	if aa >= 0:
		ans += aa
	else:
		ans -= 2 * aa
	print(ans)


from math import log, floor
t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = list(map(lambda x: int(x) % 3, input().split()))
	c = [a.count(i) for i in range(3)]
	tgt = n // 3
	s = 0
	for i in range(3):
		if c[i] > tgt:
			s += c[i] - tgt
			c[(i + 1) % 3] += c[i] - tgt
			c[i] = tgt
		else:
			s += tgt - c[i]
			c[(i + 2) % 3] -= tgt - c[i]
			c[i] = tgt
	ans.append(s)
for x in ans:
	print(x)


def ost(nums):
	(c0, c1, c2) = (0, 0, 0)
	for i in nums:
		if i % 3 == 0:
			c0 += 1
		if i % 3 == 1:
			c1 += 1
		if i % 3 == 2:
			c2 += 1
	return (c0, c1, c2)
for _ in range(int(input())):
	d = input()
	nums = input().split()
	nums = [int(n) for n in nums]
	s = 0
	(c0, c1, c2) = ost(nums)
	sr = (c0 + c1 + c2) // 3
	while True:
		while c0 > sr:
			c0 -= 1
			c1 += 1
			s += 1
		while c1 > sr:
			c1 -= 1
			c2 += 1
			s += 1
		while c2 > sr:
			c2 -= 1
			c0 += 1
			s += 1
		if c0 == c1 and c1 == c2 and (c0 == c2):
			break
	print(s)


def find_divisors(a_list):
	(c0, c1, c2) = (0, 0, 0)
	for i in a_list:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	return (c0, c1, c2)
repeat = int(input())
for rep in range(repeat):
	length = int(input())
	div_arr = list(map(int, input().split()))
	(c0, c1, c2) = find_divisors(div_arr)
	operations = 0
	standard = length // 3
	subtract = 0
	while True:
		if c0 > standard:
			subtract = c0 - standard
			c0 -= subtract
			c1 += subtract
			operations += subtract
		if c1 > standard:
			subtract = c1 - standard
			c1 -= subtract
			c2 += subtract
			operations += subtract
		if c2 > standard:
			subtract = c2 - standard
			c2 -= subtract
			c0 += subtract
			operations += subtract
		if c1 == standard and c0 == standard and (c2 == standard):
			break
	print(operations)


import math
from collections import defaultdict
DEBUG = True

def log(*args, **kwargs):
	if DEBUG:
		print(*args, **kwargs)

def rint():
	return int(input())

def rlist(f=int):
	return list(map(f, input().split()))

def rstr():
	return input()

class Solution:

	def __init__(self):
		pass

	def run(self):
		n = rint()
		a = rlist()
		rem = [0] * 3
		total = 0
		equal = n // 3
		for x in a:
			rem[x % 3] += 1
			total += x
		result = 0
		for i in range(6):
			if rem[i % 3] > equal:
				diff = rem[i % 3] - equal
				result += diff
				rem[(i + 1) % 3] += diff
				rem[i % 3] = equal
		return result
t = int(input())
s = Solution()
for i in range(t):
	print(s.run())


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	A = [a % 3 for a in map(int, input().split())]
	D = [A.count(i) for i in range(3)]
	res = 0
	f = n // 3
	while True:
		for i in range(3):
			if D[i] > f:
				D[(i + 1) % 3] += D[i] - f
				res += D[i] - f
				D[i] = f
		if len(set(D)) == 1:
			break
	print(res)

def resolve():
	t = int(input())
	for _ in range(t):
		solve()
resolve()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(x, y, z) = (0, 0, 0)
	c = 0
	for i in range(n):
		if l[i] % 3 == 0:
			x += 1
		elif l[i] % 3 == 1:
			y += 1
		else:
			z += 1
	m = n // 3
	while x != m or y != m or z != m:
		if x > m:
			c += x - m
			y += x - m
			x = m
		if y > m:
			c += y - m
			z += y - m
			y = m
		if z > m:
			c += z - m
			x += z - m
			z = m
	print(c)


t = int(input())
res = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0, 0, 0]
	for i in range(n):
		c[a[i] % 3] += 1
	j = n // 3
	i = 0
	count = 0
	while c[0] != c[1] or c[0] != c[2]:
		if c[i] > j:
			c[(i + 1) % 3] += c[i] - j
			count += c[i] - j
			c[i] = j
		i += 1
		i %= 3
	res.append(count)
for i in res:
	print(i)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	c0 = c1 = c2 = 0
	k = n // 3
	for i in arr:
		if not i % 3:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	while c0 != k or c1 != k:
		if c0 > k and c1 < k:
			c0 -= 1
			c1 += 1
			count += 1
		elif c1 > k and c2 < k:
			c1 -= 1
			c2 += 1
			count += 1
		elif c2 > k and c0 < k:
			c2 -= 1
			c0 += 1
			count += 1
		elif c1 > k and c0 < k:
			c1 -= 1
			c0 += 1
			count += 2
		elif c0 > k and c2 < k:
			c0 -= 1
			c2 += 1
			count += 2
		elif c2 > k and c1 < k:
			c2 -= 1
			c1 += 1
			count += 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	r = [0, 0, 0]
	for a in arr:
		r[a % 3] += 1
	for i in range(3):
		r[i] -= n // 3
	ans = 0
	for i in range(6):
		if r[(i - 1) % 3] > 0:
			r[i % 3] += r[(i - 1) % 3]
			ans += r[(i - 1) % 3]
			r[(i - 1) % 3] = 0
	print(ans)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	u = a // 3
	ans = 0
	a = {0: 0, 1: 0, 2: 0}
	for j in l:
		a[j % 3] += 1
	j = 0
	while a[1] != a[2] or a[2] != a[0]:
		if a[j] > u:
			ans += a[j] - u
			if j != 2:
				a[j + 1] += a[j] - u
				a[j] = u * 1
				j += 1
			else:
				a[0] += a[2] - u
				a[2] = u * 1
				j = 0
		if j != 2:
			j += 1
		else:
			j = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt0 = 0
	cnt1 = 0
	cnt2 = 0
	for i in range(n):
		if lst[i] % 3 == 0:
			cnt0 += 1
		elif lst[i] % 3 == 1:
			cnt1 += 1
		else:
			cnt2 += 1
	ans = max(cnt0 - cnt2, max(cnt1 - cnt0, cnt2 - cnt1))
	print(ans)


import sys
from collections import Counter

def debug(*args):
	print(*args, file=sys.stderr)

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

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

def read_str_split():
	return list(sys.stdin.readline().strip())

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

def Main():
	t = read_int()
	for _ in range(t):
		n = read_int()
		a = read_int_list()
		good = n // 3
		ans = 0
		div_a = [x % 3 for x in a]
		cnt_a = Counter(div_a)
		while not cnt_a[0] == cnt_a[1] == cnt_a[2]:
			(key, val) = cnt_a.most_common()[0]
			if val > good:
				ans += val - good
				cnt_a[key] = good
				cnt_a[(key + 1) % 3] += val - good
		print(ans)
Main()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = n // 3
	c = [0, 0, 0]
	for i in range(n):
		if a[i] % 3 == 0:
			c[0] += 1
		if a[i] % 3 == 1:
			c[1] += 1
		if a[i] % 3 == 2:
			c[2] += 1
	cnt = 0
	while not c[0] == c[1] == c[2]:
		for i in range(3):
			if c[i - 1] > k:
				cnt += c[i - 1] - k
				c[i] += c[i - 1] - k
				c[i - 1] = k
	print(cnt)


answers = []

def solve(n, arr):
	total = 0
	one = 0
	two = 0
	zero = 0
	req = n // 3
	for ele in arr:
		if ele % 3 == 0:
			zero += 1
		elif ele % 3 == 1:
			one += 1
		else:
			two += 1
	if one == two and two == zero:
		answers.append(0)
		return
	if zero == req:
		if one > two:
			answers.append(one - req)
		else:
			answers.append((two - req) * 2)
	else:
		if zero > req:
			total += zero - req
			zero = req
			one += total
		else:
			target = req - zero
			if two > req:
				total += target
				zero = req
				two -= target
			else:
				total += 2 * target
				zero = req
				one -= target
		if one > two:
			total += one - req
			answers.append(total)
		else:
			total += (two - req) * 2
			answers.append(total)
T = int(input())
while T:
	n = int(input())
	arr = [int(x) for x in input().split()]
	solve(n, arr)
	T -= 1
for ans in answers:
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	c = [0] * 3
	for i in map(int, input().split()):
		c[i % 3] += 1
	want = n // 3
	r = 0
	while c[0] != want or c[1] != want or c[2] != want:
		w = max(c[2] - want, 0)
		c[2] -= w
		r += w
		c[0] += w
		w = max(c[0] - want, 0)
		c[0] -= w
		r += w
		c[1] += w
		w = max(c[1] - want, 0)
		c[1] -= w
		r += w
		c[2] += w
	print(r)
for i in range(int(input())):
	solve()


import math
result = []
cases = int(input())
for i in range(cases):
	sum = 0
	num = int(input())
	ain = list(map(int, input().split(' ')))
	dt = {}
	dt[0] = 0
	dt[1] = 0
	dt[2] = 0
	for j in ain:
		dt[j % 3] = dt[j % 3] + 1
	for l in range(2):
		for m in range(3):
			if dt[m] > num / 3:
				diff = dt[m] - num / 3
				dt[m] = num / 3
				dt[(m + 1) % 3] += diff
				sum += diff
	result.append(int(sum))
for _ in result:
	print(_)


import sys

def f2(a, n):
	c0 = 0
	c1 = 0
	c2 = 0
	for i in range(n):
		if a[i] % 3 == 0:
			c0 = c0 + 1
		if a[i] % 3 == 1:
			c1 = c1 + 1
		if a[i] % 3 == 2:
			c2 = c2 + 1
	s = (c0 + c1 + c2) // 3
	cs = [c0, c1, c2]
	if c0 == c1 and c1 == c2:
		return 0
	t = 0
	for j in range(3):
		a = max(cs)
		i = cs.index(a)
		cs[i] = s
		if i + 1 == 3:
			i = -1
		cs[i + 1] = cs[i + 1] + a - s
		t = t + a - s
	return t
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[1 + l]
	a = data[l + 2:l + 2 + n]
	l = l + 1 + n
	print(f2(a, n))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c0, c1, c2) = (0, 0, 0)
	for i in l:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	count = 0
	if c0 == c1 and c1 == c2:
		print(0)
		continue
	else:
		a = n // 3
		if c0 < a:
			r = a - c0
			if c2 > a:
				if c2 >= a + r:
					count += r
					c2 -= r
				else:
					count = count + c2 - a + 2 * (c1 - a)
			else:
				count += r * 2
				c1 -= r
		if c1 < a:
			r = a - c1
			if c0 > a:
				if c0 >= a + r:
					count += r
					c0 -= r
				else:
					count = count + c0 - a + 2 * (c2 - a)
			else:
				count += r * 2
				c2 -= r
		if c2 < a:
			r = a - c2
			if c1 > a:
				if c1 >= a + r:
					count += r
					c1 -= r
				else:
					count = count + c1 - a + 2 * (c0 - a)
			else:
				count += r * 2
				c0 -= r
	print(count)


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	c = [0] * 3
	res = 0
	for i in a:
		c[i % 3] += 1
	for k in range(3):
		for i in range(3):
			if c[i] > n // 3:
				res += c[i] - n // 3
				c[(i + 1) % 3] += c[i] - n // 3
				c[i] = n // 3
	ans.append(res)
for i in ans:
	print(i)


T = int(input())
while T > 0:
	c0 = 0
	c1 = 0
	c2 = 0
	X = int(input())
	N = input().split()
	A = 0
	for x in N:
		if int(x) % 3 == 0:
			c0 += 1
		elif int(x) % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	if c0 == c1 and c1 == c2:
		print(0)
	else:
		while c0 != c1 or c1 != c2:
			if c0 > X / 3:
				c1 += c0 - X / 3
				A += c0 - X / 3
				c0 = X / 3
			if c1 > X / 3:
				c2 += c1 - X / 3
				A += c1 - X / 3
				c1 = X / 3
			if c2 > X / 3:
				c0 += c2 - X / 3
				A += c2 - X / 3
				c2 = X / 3
		print(int(A))
	T -= 1


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, A):
	target = N // 3
	freq = Counter((x % 3 for x in A))
	ans = 0
	for i in range(9):
		if freq[i % 3] >= target:
			diff = freq[i % 3] - target
			freq[i % 3] -= diff
			freq[(i + 1) % 3] += diff
			ans += diff
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, A)
	print(ans)


def balance_remainder(arr, n):
	f = {0: 0, 1: 0, 2: 0}
	for i in range(n):
		r = arr[i] % 3
		f[r] += 1
	b = n / 3
	ans = 0
	for i in range(2):
		if f[0] > b:
			ans += f[0] - b
			f[1] += f[0] - b
			f[0] = b
		if f[1] > b:
			ans += f[1] - b
			f[2] += f[1] - b
			f[1] = b
		if f[2] > b:
			ans += f[2] - b
			f[0] += f[2] - b
			f[2] = b
	return int(ans)
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	print(balance_remainder(arr, n))
	t -= 1


I = input
for _ in range(int(I())):
	n = int(I())
	c = [0] * 3
	for i in I().split():
		c[int(i) % 3] += 1
	print(max((c[i] - c[i - 1] for i in (0, 1, 2))))


for _ in range(int(input())):
	input()
	c = [0, 0, 0]
	for i in list(map(int, input().split())):
		c[i % 3] += 1
	cc = sum(c) // 3
	cs = [cc - c[0], cc - c[1], cc - c[2]]
	i = 0
	k = 0
	p = 0
	while cs[0] != 0 or cs[1] != 0 or cs[2] != 0:
		if cs[i] < 0:
			p -= cs[i]
			cs[i] = 0
		else:
			da = min(p, cs[i])
			p -= da
			cs[i] -= da
		i += 1
		k += p
		if i > 2:
			i = 0
	print(k)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def solve():
	n = itg()
	cc = [0] * 3
	for a in mpint():
		cc[a % 3] += 1
	k = n // 3
	ans = 0
	for _ in range(3):
		if cc[0] == cc[1] == cc[2]:
			break
		if cc[0] > k:
			d = cc[0] - k
			cc[0] = k
			cc[1] += d
			ans += d
		if cc[1] > k:
			d = cc[1] - k
			cc[1] = k
			cc[2] += d
			ans += d
		if cc[2] > k:
			d = cc[2] - k
			cc[2] = k
			cc[0] += d
			ans += d
	return ans

def main():
	for _ in range(itg()):
		print(solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/1490/problem/B'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 3:
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG:
		_print = print

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


t = input()
d = []
for i in range(int(t)):
	b = input()
	ab = list(map(int, input().split()))
	d.append(ab)

def an(a):
	c0 = 0
	c1 = 0
	c2 = 0
	le = len(a) // 3
	for i in a:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	if max(c0, c1, c2) == c1:
		cc = [c1, c2, c0]
	elif max(c0, c1, c2) == c2:
		cc = [c2, c0, c1]
	else:
		cc = [c0, c1, c2]
	c = cc[0] - le
	cc[1] = cc[1] + c
	if cc[1] >= le:
		c += cc[1] - le
	else:
		c = c + 2 * (cc[2] - le)
	print(c)
for i in d:
	an(i)


def check(lst, r):
	for i in lst:
		if i != r:
			return 0
	return 1

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	zer = 0
	one = 0
	two = 0
	for i in a:
		if i % 3 == 0:
			zer += 1
		elif i % 3 == 1:
			one += 1
		else:
			two += 1
	r = n // 3
	lst = [zer, one, two]
	count = 0
	i = 0
	while 1:
		if lst[i] > r:
			rem = lst[i] - r
			lst[i] -= rem
			count += rem
			if i == 2:
				i = -1
			lst[i + 1] += rem
		if check(lst, r):
			break
		i += 1
	return count
for t in range(0, int(input())):
	print(solve())


def func(n, f):
	zero = 0
	one = 0
	two = 0
	x = n // 3
	for i in range(n):
		if f[i] % 3 == 0:
			zero = zero + 1
		elif f[i] % 3 == 1:
			one = one + 1
		elif f[i] % 3 == 2:
			two = two + 1
	k = 0
	while True:
		if zero == one and one == two:
			return k
		if zero > x:
			c = zero - x
			zero = x
			one = one + c
			k = k + c
		if one > x:
			c = one - x
			one = x
			two = two + c
			k = k + c
		if two > x:
			c = two - x
			two = x
			zero = zero + c
			k = k + c
x = int(input())
lis = []
for i in range(x):
	n = int(input())
	f = list(map(int, input().split()))
	ans = func(n, f)
	lis.append(ans)
for i in lis:
	print(i)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
for _ in range(inp()):
	n = inp()
	x = ip()
	y = [i % 3 for i in x]
	dt = {0: 0, 1: 0, 2: 0}
	for i in y:
		dt[i] = dt.get(i, 0) + 1
	if dt[0] == dt[1] == dt[2]:
		print(0)
		continue
	d = n // 3
	ans = 0
	for i in range(6):
		(a, b) = (i % 3, (i + 1) % 3)
		if dt[a] > d:
			diff = dt[a] - d
			dt[a] -= diff
			dt[b] += diff
			ans += diff
	print(ans)


from collections import defaultdict

def solution():
	t = int(input())
	out = ''
	while t > 0:
		n = int(input())
		a = list(map(int, input().split(' ')))
		c0 = c1 = c2 = cnt = 0
		for i in range(0, len(a)):
			if a[i] % 3 == 0:
				c0 += 1
			elif a[i] % 3 == 1:
				c1 += 1
			else:
				c2 += 1
		if c0 == c1 == c2:
			out += '0\n'
		else:
			ttl = int(n / 3)
			if c2 > ttl:
				cnt = cnt + c2 - ttl
				c0 = c0 + c2 - ttl
			else:
				cnt = cnt + ttl - c2
				c1 = c1 - (ttl - c2)
			if c1 > ttl:
				cnt += 2 * (c1 - ttl)
				c0 = c0 + (c1 - ttl)
			else:
				cnt = cnt + (ttl - c1)
				c0 = c0 - (ttl - c1)
			out += str(cnt) + '\n'
		t -= 1
	print(out)
solution()


import math as m
q = 1
q = int(input())

def fn(a, b):
	if a < b:
		return b - a
	return (a - b) // 2
while q:
	q -= 1
	n = int(input())
	a = list(map(int, input().split()))
	x = [0] * 3
	for y in a:
		x[y % 3] += 1
	(a[0], a[1], a[2]) = (x[0], x[1], x[2])
	ans = 0
	if a[0] == n // 3:
		ans = fn(a[1], a[2])
	elif a[0] > n // 3:
		ans += a[0] - n // 3
		a[1] += ans
		ans += fn(a[1], a[2])
	else:
		req = n // 3 - a[0]
		if a[2] >= req:
			ans += req
			a[2] -= req
			ans += fn(a[1], a[2])
		else:
			ans += req * 2
			a[1] -= req
			ans += fn(a[1], a[2])
	print(ans)


t = int(input())
result_array = []
for i in range(t):
	n = int(input())
	c = [0, 0, 0]
	l = list(map(int, input().split()))
	aux = n / 3
	result = 0
	for el in l:
		c[el % 3] += 1
	for j in range(2):
		if c[0] > aux:
			result += c[0] - aux
			c[1] += c[0] - aux
			c[0] = aux
		if c[1] > aux:
			result += c[1] - aux
			c[2] += c[1] - aux
			c[1] = aux
		if c[2] > aux:
			result += c[2] - aux
			c[0] += c[2] - aux
			c[2] = aux
	result_array.append(int(result))
for res in result_array:
	print(res)


import math
t = int(input())
for i in range(t):
	N = int(input())
	n = N / 3
	a = list(map(int, input().split()))
	c0 = 0
	c2 = 0
	c1 = 0
	res = 0
	for k in range(N):
		if a[k] % 3 == 0:
			c0 = c0 + 1
		if a[k] % 3 == 2:
			c2 = c2 + 1
	c1 = N - c0 - c2
	c = [c0, c1, c2]
	p = 0
	for i in range(1, 3):
		if c[i] > c[0]:
			p = i
	c[(p + 1) % 3] = c[(p + 1) % 3] + (c[p] - n)
	res = res + (c[p] - n)
	if c[(p + 1) % 3] > c[(p + 2) % 3]:
		res = res + (c[(p + 1) % 3] - c[(p + 2) % 3]) / 2
	else:
		res = res + c[(p + 2) % 3] - c[(p + 1) % 3]
	print(int(res))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	(c0, c1, c2) = (0, 0, 0)
	for i in range(n):
		if a[i] % 3 == 0:
			c0 += 1
		if a[i] % 3 == 1:
			c1 += 1
		if a[i] % 3 == 2:
			c2 += 1
	aim = (c0 + c1 + c2) // 3
	res = 0
	if max(c0, c1, c2) == c0:
		m = c0
		nex = c1
		nexnex = c2
	elif max(c0, c1, c2) == c1:
		m = c1
		nex = c2
		nexnex = c0
	else:
		m = c2
		nex = c0
		nexnex = c1
	if nexnex <= aim:
		print(m - nexnex)
	else:
		print(m - aim + (nexnex - aim) * 2)


n = int(input())

def solve_test():
	n = int(input())
	a = [int(x) for x in input().split()]
	c = [0, 0, 0]
	for x in a:
		y = x % 3
		c[y] += 1
	res = 0
	while max(c) != n // 3:
		i = c.index(max(c))
		d = c[i] - n // 3
		res += d
		c[i] -= d
		c[(i + 1) % 3] += d
	print(res)
for i in range(n):
	solve_test()


import math
for w in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c0 = 0
	c1 = 0
	c2 = 0
	for i in range(n):
		if a[i] % 3 == 0:
			c0 += 1
		elif a[i] % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	c = max(c0, c1, c2)
	ans = 0
	if c0 == c1 and c1 == c2:
		print(0)
	else:
		s = (c0 + c1 + c2) // 3
		if c == c0:
			if c1 > s:
				ans += abs(c0 - s) * 2 + (c1 - s)
			elif c2 > s:
				ans += abs(c0 - s) + 2 * abs(c2 - s)
			else:
				ans += abs(s - c1) + 2 * abs(c2 - s)
		elif c1 == c:
			ans += 0
			if c2 > s:
				ans += c2 - s + abs(c1 - s) * 2
			elif c0 > s:
				ans += c1 - s + 2 * abs(c0 - s)
			else:
				ans += abs(c2 - s) + abs(c0 - s) * 2
		elif c0 > s:
			ans += abs(c0 - s) + abs(c2 - s) * 2
		elif c1 > s:
			ans += abs(c2 - s) + abs(c1 - s) * 2
		else:
			ans += abs(c0 - s) + abs(c1 - s) * 2
		print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	t = [0, 0, 0]
	for c in arr:
		t[c % 3] += 1
	k = n // 3
	ans = 0
	for i in range(6):
		if t[i % 3] > k:
			ans += t[i % 3] - k
			t[(i + 1) % 3] += t[i % 3] - k
			t[i % 3] = k
	print(ans)


c0 = c1 = c2 = 0

def compute_remainders(lst):
	global c0, c1, c2
	for x in lst:
		if x % 3 == 0:
			c0 += 1
		elif x % 3 == 1:
			c1 += 1
		else:
			c2 += 1

def max_three(a, b, c):
	if a >= b and a >= c:
		return a
	elif b >= a and b >= c:
		return b
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	c0 = c1 = c2 = 0
	compute_remainders(lst)
	if c0 == c1 and c0 == c2:
		print(0)
	else:
		value = int((c0 + c1 + c2) / 3)
		nr = 0
		while True:
			if c0 == c1 and c0 == c2:
				print(nr)
				break
			if c0 == max_three(c0, c1, c2):
				c0 -= 1
				c1 += 1
			elif c1 == max_three(c0, c1, c2):
				c1 -= 1
				c2 += 1
			else:
				c2 -= 1
				c0 += 1
			nr += 1


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

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

def getliststr():
	return list(stdin.readline().split())

def getint():
	return int(stdin.readline().strip())

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

def pr(s):
	stdout.write(str(s) + '\n')

def prlist(l):
	stdout.write(' '.join(list(map(str, l))) + '\n')

def distribute(c0, c1, c2, c):
	s = 0
	d = c0 - c
	if c1 < c:
		k = min(d, c - c1)
		s += k
		c1 -= k
		d -= k
	if c2 < c:
		k = min(d, c - c2)
		s += k * 2
		c2 -= k
		d -= k * 2
	return s
from sys import stdin, stdout
for _ in range(getint()):
	n = getint()
	a = getlistint()
	c = 0
	(c0, c1, c2) = (0, 0, 0)
	for i in range(n):
		c = a[i] % 3
		if c == 0:
			c0 += 1
		elif c == 1:
			c1 += 1
		else:
			c2 += 1
	c = n // 3
	if c0 == c1 == c2:
		pr(0)
	else:
		s = 0
		if c0 > c:
			s += distribute(c0, c1, c2, c)
		if c1 > c:
			s += distribute(c1, c2, c0, c)
		if c2 > c:
			s += distribute(c2, c0, c1, c)
		pr(s)


for i in range(int(input())):
	size = int(input())
	nums = list(map(int, input().split(' ')))
	a = []
	b = int(len(nums) / 3)
	c0 = 0
	c1 = 0
	c2 = 0
	for j in range(len(nums)):
		if nums[j] % 3 == 0:
			c0 += 1
		elif nums[j] % 3 == 1:
			c1 += 1
		elif nums[j] % 3 == 2:
			c2 += 1
	k = 0
	count = 0
	while k < 2:
		if c0 > b:
			e1 = c0 - b
			c0 -= e1
			c1 += e1
			count += e1
		if c1 > b:
			e1 = c1 - b
			c1 -= e1
			c2 += e1
			count += e1
		if c2 > b:
			e1 = c2 - b
			c2 -= e1
			c0 += e1
			count += e1
		k += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(map(lambda x: x % 3, l))
	eq = n // 3
	a = l.count(0)
	b = l.count(1)
	c = l.count(2)
	times = 0
	if a > eq:
		inc = a - eq
		times += inc
		b += inc
		a = eq
	if b > eq:
		inc = b - eq
		times += inc
		c += inc
		b = eq
	if c > eq:
		inc = c - eq
		times += inc
		a += inc
		c = eq
	if a > eq:
		inc = a - eq
		times += inc
	print(times)


import sys
import math
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	C = [0, 0, 0]
	for a in A:
		if a % 3 == 0:
			C[0] += 1
		if a % 3 == 1:
			C[1] += 1
		if a % 3 == 2:
			C[2] += 1
	bnum = n // 3
	ans = 0
	g = [[0, 1, 2], [2, 0, 1], [1, 2, 0]]
	while C[0] < bnum or C[1] < bnum or C[2] < bnum:
		i = C.index(min(C))
		j = C.index(max(C))
		how = min(abs(max(C) - bnum), abs(min(C) - bnum))
		C[i] += how
		C[j] -= how
		ans += g[j][i] * how
	print(ans)


def solve():
	n = int(input())
	arr = [int(i) for i in input().split()]
	c = [0, 0, 0]
	for i in arr:
		c[i % 3] += 1
	it = 0
	while c[0] != c[1] or c[0] != c[2] or c[1] != c[2]:
		max_c = max(c)
		max_i = c.index(max_c)
		c[(max_i + 1) % 3] += 1
		c[max_i] -= 1
		it += 1
	print(str(it))
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = map(int, input().split())
	a = 0
	b = 0
	c = 0
	for i in l:
		if i % 3 == 0:
			a += 1
		elif i % 3 == 1:
			b += 1
		else:
			c += 1
	avg = n / 3
	cost = 0
	if a > avg:
		cost += a - avg
		b += a - avg
		a = avg
	if b > avg:
		cost += b - avg
		c += b - avg
		b = avg
	if c > avg:
		cost += c - avg
		a += c - avg
		c = avg
	if a > avg:
		cost += a - avg
		b += a - avg
		a = avg
	print(int(cost))


for _ in range(int(input())):
	n = int(input())
	dic = {0: 0, 1: 0, 2: 0}
	arr = list(map(int, input().split()))
	for i in range(n):
		rem = arr[i] % 3
		dic[rem] += 1
	c1 = dic[1]
	c2 = dic[2]
	c0 = dic[0]
	counter = 0
	while c1 != c2 or c2 != c0 or c1 != c0:
		if c2 > c0:
			counter += 1
			c0 += 1
			c2 -= 1
		elif c0 > c1:
			counter += 1
			c1 += 1
			c0 -= 1
		elif c1 > c2:
			counter += 1
			c2 += 1
			c1 -= 1
	print(counter)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	(c0, c1, c2) = (0, 0, 0)
	for i in a:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	c = n // 3
	ans = 0
	while c1 != c or c2 != c or c0 != c:
		if c0 > c:
			ans += c0 - c
			c1 += c0 - c
			c0 = c
		if c1 > c:
			ans += c1 - c
			c2 += c1 - c
			c1 = c
		if c2 > c:
			ans += c2 - c
			c0 += c2 - c
			c2 = c
	print(ans)


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		(c1, c0, c2) = (0, 0, 0)
		c = [0] * 3
		for i in l:
			if i % 3 == 0:
				c[0] += 1
			elif i % 3 == 1:
				c[1] += 1
			else:
				c[2] += 1
		s = 0
		i = c.index(max(c))
		while c[i] != n // 3:
			x = c[i] - n // 3
			if i == 2:
				c[i] = n // 3
				c[0] += x
			else:
				c[i] = n // 3
				c[i + 1] += x
			s += x
			i = c.index(max(c))
		print(s)
main()


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	c0 = n // 3
	c1 = n // 3
	c2 = n // 3
	res = 0
	for i in range(n):
		k = li[i] % 3
		if k == 0:
			if c0 > 0:
				c0 -= 1
			elif c1 > 0:
				c1 -= 1
				res += 1
			else:
				c2 -= 1
				res += 2
		elif k == 1:
			if c1 > 0:
				c1 -= 1
			elif c2 > 0:
				c2 -= 1
				res += 1
			else:
				c0 -= 1
				res += 2
		elif k == 2:
			if c2 > 0:
				c2 -= 1
			elif c0 > 0:
				c0 -= 1
				res += 1
			else:
				c1 -= 1
				res += 2
	print(res)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	average = n // 3
	counts = [0, 0, 0]
	for a_i in A:
		counts[a_i % 3] += 1
	moves = 0
	for i in range(5):
		if counts[i % 3] > average:
			cost = counts[i % 3] - average
			counts[i % 3] -= cost
			moves += cost
			counts[(i + 1) % 3] += cost
	print(moves)


for _ in range(int(input())):
	n = int(input())
	array = [int(x) for x in input().split()]
	modulus = []
	count = [0, 0, 0]
	total_count = 0
	for x in array:
		modulus.append(x % 3)
		if x % 3 == 0:
			count[0] += 1
		elif x % 3 == 1:
			count[1] += 1
		else:
			count[2] += 1
	while True:
		max_index = count.index(max(count))
		next_index = (max_index + 1) % 3
		add = count[max_index] - n // 3
		total_count = total_count + add
		count[next_index] = count[next_index] + add
		count[max_index] = count[max_index] - add
		if count[0] == count[1] and count[1] == count[2]:
			print(total_count)
			break


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	(c0, c1, c2) = (0, 0, 0)
	for i in arr:
		if i % 3 == 0:
			c0 += 1
		elif i % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	res = 0
	for i in range(2):
		if c0 > n // 3:
			res += c0 - n // 3
			c1 += c0 - n // 3
			c0 = n // 3
		if c1 > n // 3:
			res += c1 - n // 3
			c2 += c1 - n // 3
			c1 = n // 3
		if c2 > n // 3:
			res += c2 - n // 3
			c0 += c2 - n // 3
			c2 = n // 3
	return res

def main():
	for _ in range(int(input())):
		print(solve())
main()


n = int(input())
for i in range(n):
	a = int(input())
	l1 = list(map(int, input().split()))
	a = int(a / 3)
	c = [0, 0, 0]
	for j in l1:
		if j % 3 == 0:
			c[0] = c[0] + 1
		elif j % 3 == 1:
			c[1] = c[1] + 1
		else:
			c[2] = c[2] + 1
	count = 0
	while c != [a, a, a]:
		if c[0] > a:
			count = count + c[0] - a
			c[1] = c[1] + c[0] - a
			c[0] = a
		if c[1] > a:
			count = count + c[1] - a
			c[2] = c[2] + c[1] - a
			c[1] = a
		if c[2] > a:
			count = count + c[2] - a
			c[0] = c[0] + c[2] - a
			c[2] = a
	print(count)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	t = n // 3
	a = list(map(int, stdin.readline().split()))
	res = 0
	b = [0, 0, 0]
	for i in a:
		b[i % 3] += 1
	for i in range(3):
		c = i % 3
		if b[c] > t:
			diff = b[c] - t
			if b[(c + 1) % 3] < t:
				move_1 = min(diff, t - b[(c + 1) % 3])
				res += move_1
				b[c] -= move_1
				diff -= move_1
				b[(c + 1) % 3] += move_1
			if b[(c + 2) % 3] < t:
				move_2 = min(diff, t - b[(c + 2) % 3])
				res += 2 * move_2
				b[c] -= move_2
				diff -= move_2
				b[(c + 2) % 3] += move_2
	print(res)


import sys
inputlines = sys.stdin.readlines()
number_of_testcases = int(inputlines[0])
for i in range(number_of_testcases):
	n = int(inputlines[2 * i + 1])
	array_given = list(map(int, inputlines[2 * i + 2].split(' ')))
	c_list = [0, 0, 0]
	for j in array_given:
		c_list[j % 3] += 1
	every_c_should_be = n // 3
	number_of_steps_needed = 0
	j = 0
	k = 1
	for _ in range(4):
		if c_list[j] > every_c_should_be:
			extra_in_cj = c_list[j] - every_c_should_be
			c_list[k] += extra_in_cj
			c_list[j] = every_c_should_be
			number_of_steps_needed += extra_in_cj
		j = (j + 1) % 3
		k = (k + 1) % 3
	print(number_of_steps_needed)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	cnt = defaultdict(int)
	for i in arr:
		cnt[i % 3] += 1
	avg = cnt[0] + cnt[1] + cnt[2]
	avg = avg // 3
	res = max(cnt[0], cnt[1], cnt[2])
	if res == cnt[0]:
		if cnt[2] > avg:
			ans = avg - cnt[1] + (cnt[2] - avg)
		elif cnt[1] + cnt[2] < avg:
			ans = avg + cnt[1] + (avg - cnt[1] - cnt[2]) * 2
		else:
			ans = avg - cnt[2] + avg - (cnt[1] - (avg - cnt[2]))
	elif res == cnt[1]:
		if cnt[0] > avg:
			ans = avg - cnt[2] + (cnt[0] - avg)
		elif cnt[2] + cnt[0] < avg:
			ans = avg + cnt[2] + (avg - cnt[2] - cnt[0]) * 2
		else:
			ans = avg - cnt[0] + avg - (cnt[2] - (avg - cnt[0]))
	elif cnt[1] > avg:
		ans = avg - cnt[0] + (cnt[1] - avg)
	elif cnt[0] + cnt[1] < avg:
		ans = avg + cnt[0] + (avg - cnt[0] - cnt[1]) * 2
	else:
		ans = avg - cnt[1] + avg - (cnt[0] - (avg - cnt[1]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {0: 0, 1: 0, 2: 0}
	for i in arr:
		d[i % 3] += 1
	c = n // 3
	h = 0
	idx = -1
	kdx = -1
	for i in d:
		if d[i] >= c:
			h += 1
			idx = i
		else:
			kdx = i
	out = 0
	if h == 1:
		for i in d:
			if i != idx:
				if (idx + 2) % 3 == i:
					out += c - d[i]
				out += c - d[i]
	elif kdx == 2:
		out = 2 * (d[0] - c) + d[1] - c
	elif kdx == 1:
		out = d[0] - c + 2 * (d[2] - c)
	elif kdx == 0:
		out = d[2] - c + 2 * (d[1] - c)
	print(out)


import math

def getlist():
	return [int(i) for i in input().split()]

def getmany():
	return map(int, input().split())

def getstr():
	return [str(i) for i in input().split()]

def solve():
	n = int(input())
	a = getlist()
	c0 = 0
	c2 = 0
	c1 = 0
	for i in a:
		if i % 3 == 1:
			c1 += 1
		elif i % 3 == 2:
			c2 += 1
		else:
			c0 += 1
	ans = 0
	c = c0 + c1 + c2
	aver = c // 3
	x = c0 - aver
	y = c1 - aver
	z = c2 - aver
	while x > 0 and y < 0:
		if y < 0:
			ans += 1
			y += 1
			x -= 1
	while y > 0 and z < 0:
		if z < 0:
			ans += 1
			z += 1
			y -= 1
	while z > 0 and x < 0:
		if x < 0:
			ans += 1
			x += 1
			z -= 1
	while x > 0 and z < 0:
		if z < 0:
			ans += 2
			z += 1
			x -= 1
	while y > 0 and x < 0:
		if x < 0:
			ans += 2
			x += 1
			y -= 1
	while z > 0 and y < 0:
		if y < 0:
			ans += 2
			y += 1
			z -= 1
	print(ans)
for _ in range(int(input())):
	solve()