Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

Chef has an array A of length N.

Since Chef's favorite number is 3, he wants to make all numbers in the array a multiple of 3.

Chef can do the following operation:
Select any 2 different indices i and j and increase A_{i} by 1 and decrease A_{j} by 1.

Help Chef find out the minimum number of operations required (or report its not possible) to achieve his objective.

------ Input Format ------ 

- The first line will contain T, the number of test cases. Then the test cases follow.
- The first line of each test case contains N, denoting the length of the array.
- The second line of each testcase contains N space separated integers A_{i}.

------ Output Format ------ 

Output the minimum number of operations required to make all numbers divisible by 3.

If it is not possible to make every number divisible by 3, then output -1.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
3
1 2 3
4
6 3 9 12
2
4 3

----- Sample Output 1 ------ 
1
0
-1

----- explanation 1 ------ 
Test Case $1$: Chef can select the indices $2$ and $1$ and thus increase $A_{2}$ by $1$ and decrease $A_{1}$ by $1$. Thus the array becomes $[0,3,3]$. So every number is now divisible by $3$.

Test Case $2$: Since all the numbers are already multiples of $3$, Chef will not need to apply the operation at all.

Test Case $3$: There is no way to make all the numbers a multiple of $3$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {1: 0, 2: 0, 0: 0}
	for i in a:
		d[i % 3] += 1
	if abs(d[1] - d[2]) % 3 == 0:
		print(min(d[1], d[2]) + 2 * (abs(d[1] - d[2]) // 3))
	else:
		print(-1)


t = int(input())
for item in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = [0] * n
	for i in range(0, len(l)):
		res[i] = l[i] % 3
	one_count = res.count(1)
	two_count = res.count(2)
	if sum(l) % 3 != 0:
		print(-1)
	else:
		print(min(one_count, two_count) + abs(one_count - two_count) // 3 * 2)


import math
T = int(input())
for a in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	K = []
	for i in range(N):
		K.append(L[i] % 3)
	c = K.count(1)
	d = K.count(2)
	if c == d:
		print(c)
	elif abs(c - d) % 3:
		print(-1)
	else:
		print(abs(c - d) // 3 * 2 + min(c, d))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(a, b) = (0, 0)
	for j in range(n):
		if l[j] % 3 == 1:
			a += 1
		elif l[j] % 3 == 2:
			b += 1
	if abs(a - b) % 3 == 0:
		print(min(a, b) + abs(a - b) // 3 * 2)
	else:
		print(-1)


def listin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = int(input())
	a = input().split()
	nos = [0, 0, 0, 0]
	for i in range(n):
		a[i] = int(a[i]) % 3
		nos[a[i]] += 1
	ans = m = min(nos[1], nos[2])
	mm = max(nos[1], nos[2])
	diff = mm - m
	if diff % 3 == 0:
		print(ans + diff * 2 // 3)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	(one, two) = (0, 0)
	for i in range(n):
		if l[i] % 3 == 1:
			one += 1
		elif l[i] % 3 == 2:
			two += 1
	if abs(one - two) % 3 == 0:
		print(min(one, two) + abs(one - two) // 3 * 2)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	(a, b) = (0, 0)
	for i in range(N):
		if l[i] % 3 == 1:
			a += 1
		elif l[i] % 3 == 2:
			b += 1
	if abs(a - b) % 3 == 0:
		print(min(a, b) + abs(a - b) * 2 // 3)
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	r1 = len(list(filter(lambda x: x % 3 == 1, A)))
	r2 = len(list(filter(lambda x: x % 3 == 2, A)))
	if r1 == r2:
		print(r1)
		continue
	t = abs(r1 - r2)
	if t % 3 == 0:
		print(min(r1, r2) + t // 3 * 2)
	else:
		print(-1)


try:
	t = int(input())
	while t > 0:
		n = int(input())
		a = list(map(int, input().split()))[:n]
		count1 = 0
		count2 = 0
		for i in range(0, n):
			if a[i] % 3 == 1:
				count1 += 1
			if a[i] % 3 == 2:
				count2 += 1
		if abs(count1 - count2) % 3 == 0:
			print(min(count1, count2) + abs(count1 - count2) // 3 * 2)
		else:
			print(-1)
		t -= 1
except EOFError as e:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	mod = [el % 3 for el in list(map(int, input().split()))]
	if sum(mod) % 3 == 0:
		(m1, m2) = (mod.count(1), mod.count(2))
		print(min(m1, m2) + 2 * abs(m1 - m2) // 3)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ones = twos = 0
	for i in arr:
		if i % 3 == 1:
			ones += 1
		elif i % 3 == 2:
			twos += 1
	if sum(arr) % 3 != 0:
		print(-1)
	elif ones == twos == 0:
		print(0)
	else:
		count = 0
		val = min(twos, ones)
		twos -= val
		ones -= val
		count += val + max(twos, ones) / 3 * 2
		print(int(count))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(lambda x: int(x) % 3, input().split()))
	c = Counter(arr)
	total = min(c[1], c[2])
	left = max(c[1], c[2]) - total
	if left % 3 != 0:
		print(-1)
	else:
		print(total + left // 3 * 2)


for _ in range(int(input())):
	n = int(input())
	arr = [0, 0, 0]
	for num in map(int, input().split()):
		arr[num % 3] += 1
	if (arr[1] + arr[2] * 2) % 3 == 0:
		ans = 0
		temp = min(arr[1], arr[2])
		ans += temp
		arr[1] -= temp
		arr[2] -= temp
		ans += 2 * (arr[1] // 3 + arr[2] // 3)
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(ro, rt, flag) = (0, 0, 0)
	for i in l:
		if i % 3 == 1:
			flag += 1
			ro += 1
		elif i % 3 == 2:
			flag += 2
			rt += 1
	if flag % 3 == 0:
		if ro == rt:
			ans = ro
		elif ro > rt:
			ans = rt
			ro -= rt
			if ro % 3 == 0:
				ans += 2 * (ro // 3)
			else:
				ans = -1
		else:
			ans = ro
			rt -= ro
			if rt % 3 == 0:
				ans += 2 * (rt // 3)
			else:
				ans = -1
		print(ans)
	else:
		print(-1)


T = int(input())
for t in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	K = []
	for i in range(N):
		K.append(L[i] % 3)
	c = K.count(1)
	d = K.count(2)
	if c == d:
		print(c)
	elif c % 3 == d % 3:
		x = min(c, d)
		diff = abs(c - d)
		if diff % 3 == 0:
			y = diff / 3 * 2
			print(int(x + y))
		else:
			print(-1)
	else:
		print(-1)


def check_possibility(arr):
	(ot, tt) = (0, 0)
	for i in arr:
		x = i % 3
		if x == 1:
			ot += 1
		if x == 2:
			tt += 1
	ans = 0
	if (ot + 2 * tt) % 3 == 0:
		ans += min(ot, tt)
		ot -= ans
		tt -= ans
		ans += 2 * ((ot + tt) // 3)
		return ans
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(check_possibility(l))


def funcx(n, l1):
	o = t = 0
	for i in l1:
		if i % 3 == 1:
			o += 1
		elif i % 3 == 2:
			t += 1
	if (o - t) % 3 == 0:
		ans = min(o, t) + abs(o - t) // 3 * 2
		print(ans)
	else:
		print(-1)
	return
t = int(input())
for i in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	funcx(n, l1)


from sys import stdin
from collections import Counter
inp = stdin.readline
T = int(inp())
ans = []
for tx in range(T):
	N = int(inp())
	mcnt = Counter((int(s) % 3 for s in inp().split()))
	(zer, one, two) = (mcnt[v] for v in range(3))
	dif = abs(one - two)
	if dif % 3 == 0:
		ops = min(one, two) + 2 * (dif // 3)
		ans.append(ops)
	else:
		ans.append(-1)
print(*ans, sep='\n')


a = int(input())
for i in range(a):
	s = int(input())
	d = list(map(int, input().split()))
	r = sum(d)
	if r % 3 != 0:
		print(-1)
	else:
		r = len([x for x in d if x % 3 == 1])
		b = len([x for x in d if x % 3 == 2])
		f = abs(r - b)
		f = f - f // 3
		print(min(r, b) + f)


t = int(input())
for _ in range(0, t):
	n = int(input())
	arr = [0] * 3
	val = list(map(int, input(' ').split()))
	for i in range(0, n):
		arr[val[i] % 3] = arr[val[i] % 3] + 1
	if (arr[1] * 1 + arr[2] * 2) % 3:
		print('-1')
	else:
		ans = 0
		tmp = min(arr[1], arr[2])
		arr[1] = arr[1] - tmp
		arr[2] = arr[2] - tmp
		ans = ans + tmp
		ans = ans + 2 * (int(arr[1] / 3) + int(arr[2] / 3))
		print(ans)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	diff = [1 if x % 3 == 2 else -1 if x % 3 == 1 else 0 for x in a]
	c1 = diff.count(1)
	c2 = diff.count(-1)
	total = sum(diff)
	if total == 0:
		print(c1)
		continue
	elif total % 3 == 0:
		if total < 0:
			print(2 * (abs(total) // 3) + (c2 - abs(total)))
		else:
			print(2 * (abs(total) // 3) + (c1 - total))
	else:
		print('-1')


t = range(int(input()))
for i in t:
	n = int(input())
	l = list(map(int, input().split()))
	rem_1 = 0
	rem_2 = 0
	for j in l:
		if j % 3 == 2:
			rem_2 += 1
		if j % 3 == 1:
			rem_1 += 1
	if rem_1 == rem_2:
		print(rem_1)
	else:
		c = abs(rem_1 - rem_2)
		if c % 3 == 0:
			print(min(rem_1, rem_2) + c // 3 * 2)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	cntOne = 0
	cntTwo = 0
	for i in range(n):
		if a[i] % 3 == 1:
			cntOne += 1
		elif a[i] % 3 == 2:
			cntTwo += 1
		else:
			pass
	totalRem = cntOne + cntTwo * 2
	if totalRem % 3 == 0:
		p = abs(cntOne - cntTwo)
		if p == 0:
			print(cntOne)
		elif cntOne == 0 or cntTwo == 0:
			print(p // 3 * 2)
		else:
			print(p // 3 * 2 + min(cntTwo, cntOne))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {1: 0, 2: 0}
	if sum(l) % 3 == 0:
		for i in l:
			if i % 3 in d:
				d[i % 3] += 1
			else:
				d[i % 3] = 1
		if d[1] == d[2] == 0:
			print(0)
		elif d[1] == d[2]:
			print(d[1])
		else:
			cur = min(d[1], d[2])
			ans = max(d[1], d[2]) - cur
			ans = ans // 3 * 2
			print(ans + cur)
	else:
		print(-1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 3:
		print(-1)
		return
	(c1, c2) = (0, 0)
	for i in range(n):
		if a[i] % 3 == 1:
			c1 += 1
		elif a[i] % 3 == 2:
			c2 += 1
	(c1, c2) = (max(c1, c2), min(c1, c2))
	ans = c2 + (c1 - c2) * 2 // 3
	print(ans)
for iii in range(int(input())):
	solve()


def Min_dic(arr, n):
	c1 = c2 = c3 = 0
	s = 0
	for i in arr:
		s += i
		if i % 3 == 0:
			c1 += 1
		elif i % 3 == 1:
			c2 += 1
		else:
			c3 += 1
	if s % 3 != 0:
		return -1
	else:
		dif = abs(c2 - c3)
		count = min(c2, c3)
		count += dif // 3 * 2
	return count
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().rstrip().rsplit()))
	print(Min_dic(arr, n))


try:
	for i in range(int(input())):
		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)
		if not (b * 1 + c * 2) % 3 == 0:
			print(-1)
		else:
			t = min(b, c)
			ans = t
			b = b - t
			c = c - t
			ans = ans + 2 * (b // 3 + c // 3)
			print(ans)
except:
	pass


import math
T = int(input())
for a in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in range(N):
		l.append(a[i] % 3)
	x = l.count(1)
	y = l.count(2)
	if x == y:
		print(x)
	elif abs(x - y) % 3:
		print(-1)
	else:
		print(abs(x - y) // 3 * 2 + min(x, y))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = []
	for d in a:
		a1.append(d % 3)
	e0 = a1.count(0)
	e1 = a1.count(1)
	e2 = a1.count(2)
	l = max([e1, e2])
	l2 = min([e1, e2])
	if e1 == e2:
		print(e1)
	elif (l - l2) % 3 != 0:
		print(-1)
	else:
		print((l - l2) // 3 * 2 + l2)


try:
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		x = 0
		y = 0
		z = 0
		for i in arr:
			if i % 3 == 1:
				x += 1
			if i % 3 == 2:
				y += 1
		if y > x:
			temp = x
			x = y
			y = temp
		if x == y:
			print(x)
		elif (x - y) % 3 == 0:
			print(y + 2 * (x - y) // 3)
		else:
			print(-1)
except:
	pass


for _ in range(int(input())):
	N = int(input())
	numbers = list(map(int, input().split()))
	rem = []
	for i in range(N):
		rem.append(numbers[i] % 3)
	rem1 = rem.count(1)
	rem2 = rem.count(2)
	if rem1 == rem2:
		print(rem1)
	elif abs(rem1 - rem2) % 3:
		print(-1)
	else:
		print(abs(rem2 - rem1) // 3 * 2 + min(rem1, rem2))


def div():
	R1 = 0
	R2 = 0
	for __ in range(0, int(input())):
		N = int(input())
		my_list = list(input().strip().split(' '))
		for _ in my_list:
			n = int(_)
			if n % 3 == 1:
				R1 += 1
			elif n % 3 == 2:
				R2 += 1
		d = abs(R1 - R2)
		if d == 0:
			print(R1)
		elif d % 3 == 0:
			print(min(R1, R2) + d // 3 * 2)
		else:
			print(-1)
		R2 = 0
		R1 = 0
div()


for i in range(int(input())):
	size = int(input())
	arr = list(map(int, input().split()))

	def work(arr, size):
		rem = [0, 0, 0]
		sum = 0
		for i in arr:
			sum += i
			rem[i % 3] += 1
		if sum % 3 != 0:
			return -1
		moves = 0
		temp = min(rem[1], rem[2])
		moves += temp * 1
		rem[1] -= temp
		rem[2] -= temp
		moves += 2 * (rem[1] // 3 + rem[2] // 3)
		return moves
	print(work(arr, size))


n = int(input())
for _ in range(n):
	s = int(input())
	A = list(map(int, input().split()))
	ones = 0
	twos = 0
	for i in A:
		if i % 3 == 1:
			ones += 1
		elif i % 3 == 2:
			twos += 1
	if ones == twos:
		print(ones)
	elif (ones - twos) % 3 == 0:
		print(min(ones, twos) + abs(ones - twos) // 3 * 2)
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(a, b, c) = (0, 0, 0)
	for Ai in A:
		j = Ai % 3
		if j == 0:
			a += 1
		elif j == 1:
			b += 1
		elif j == 2:
			c += 1
	print(min(b, c) + 2 * (b + c - 2 * min(b, c)) // 3) if (b + 2 * c) % 3 == 0 else print(-1)


def check(a, n):
	one_p = 0
	one_m = 0
	for i in range(n):
		if a[i] % 3 != 0:
			if (a[i] + 1) % 3 == 0:
				one_p += 1
			else:
				one_m += 1
	if one_p == one_m:
		return one_p
	elif abs(one_p - one_m) % 3 != 0:
		return -1
	else:
		return abs(one_m - one_p) // 3 * 2 + min(one_m, one_p)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(a, n))


n = int(input())
for i in range(n):
	l = int(input())
	numbers = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	list_1 = []
	for i in range(l):
		if numbers[i] % 3 == 1:
			count1 += 1
		if numbers[i] % 3 == 2:
			count2 += 1
	x = min(count1, count2)
	y = max(count1, count2)
	if (y - x) % 3 == 0:
		print(x + 2 * (y - x) // 3)
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	sum = 0
	count1 = 0
	count2 = 0
	for i in A:
		x = i % 3
		sum = sum + x
		if x == 1:
			count1 = count1 + 1
		elif x == 2:
			count2 = count2 + 1
	y = abs(count2 - count1)
	z = min(count1, count2)
	if sum % 3 != 0:
		print('-1')
	else:
		print(z + y * 2 // 3)


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


for i in range(int(input())):
	n = int(input())
	l1 = []
	l = list(map(int, input().split(' ')))
	for i in l:
		l1.append(i % 3)
	a = len(l1)
	if sum(l1) % 3 == 0:
		a1 = l1.count(1)
		b = l1.count(2)
		c = min(a1, b)
		d = 2 * ((a1 - c) / 3 + (b - c) / 3)
		print(int(d + c))
	else:
		print('-1')


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	o = 0
	t = 0
	s = 0
	for i in range(n):
		if arr[i] % 3 == 1:
			o += 1
			s += 1
		elif arr[i] % 3 == 2:
			t += 1
			s += 2
	if s % 3 != 0:
		print(-1)
		continue
	ans = 0
	if o > t:
		ans += t
		x = o - t
		if x % 3 != 0:
			print(-1)
			continue
		x = x // 3
		ans += x * 2
		print(ans)
	elif t > o:
		ans += o
		x = t - o
		if x % 3 != 0:
			print(-1)
			continue
		x = x // 3
		ans += x * 2
		print(ans)
	else:
		print(o)


tests = int(input())
for _ in range(tests):
	n = int(input())
	a = [int(c) for c in input().split()]
	d = [0] * 3
	for c in a:
		d[c % 3] += 1
	res = min(d[1], d[2])
	d[1] -= res
	d[2] -= res
	res = res + 2 * int(d[1] / 3) + 2 * int(d[2] / 3)
	d[1] %= 3
	d[2] %= 3
	if d[1] + d[2] != 0:
		print(-1)
	else:
		print(res)


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


t = eval(input())
for i in range(t):
	n = eval(input())
	lst = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(lst[i] % 3)
	c = l.count(1)
	d = l.count(2)
	if c == d:
		print(c)
	elif abs(c - d) % 3:
		print(-1)
	else:
		print(abs(c - d) // 3 * 2 + min(c, d))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	ones = 0
	twos = 0
	ans = 0
	for i in range(n):
		if a[i] % 3 == 1:
			ones += 1
		if a[i] % 3 == 2:
			twos += 1
	ans += min(ones, twos)
	dif = abs(ones - twos)
	if dif % 3 == 0:
		ans += 2 * dif // 3
	else:
		ans = -1
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	rem = []
	for i in l1:
		if i % 3 != 0:
			rem.append(i % 3)
	if rem == []:
		print(0)
	elif sum(rem) % 3 != 0:
		print(-1)
	else:
		count = 0
		count1 = rem.count(1)
		count2 = rem.count(2)
		if count1 == count2:
			count += count1
		elif count1 > count2:
			count += count2
			count += int((count1 - count2) * 0.67)
		else:
			count += count1
			count += int((count2 - count1) * 0.67)
		print(count)


a = int(input())
while a > 0:
	z = int(input())
	l = list(map(int, input().split()))
	c = 0
	k = 0
	kl = 0
	for i in l:
		if i % 3 == 1:
			c = c + 1
		if i % 3 == 2:
			k = k + 1
	if k == c:
		print(k)
	elif k > c and (k - c) % 3 == 0:
		print(int(c + (k - c) / 3 * 2))
	elif c > k and (c - k) % 3 == 0:
		print(int(k + (c - k) / 3 * 2))
	else:
		print(-1)
	a = a - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = n = 0
	for e in a:
		m += e % 3 == 1
		n += e % 3 == 2
	res = m if m < n else n
	bal = abs(m - n)
	if bal % 3 == 0:
		res += 2 * bal // 3
	else:
		res = -1
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(m, p) = (0, 0)
	for i in l:
		if i % 3 == 1:
			m = m + 1
		elif i % 3 == 2:
			p = p + 1
	if p == m:
		print(p)
	elif m == 1 and p == 0:
		print(-1)
	elif m > p and (m - p) % 3 == 0:
		print(p + (m - p) // 3 * 2)
	elif p > m and (p - m) % 3 == 0:
		print(m + (p - m) // 3 * 2)
	else:
		print(-1)


for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = [0, 0, 0]
	for i in range(n):
		d[l[i] % 3] += 1
	m = min(d[1], d[2])
	d[1] -= m
	d[2] -= m
	d[0] = 0
	ans = m
	f = 0
	for i in range(3):
		if d[i] > 0:
			if d[i] % 3 != 0:
				f = 1
				break
			else:
				ans += d[i] // 3 * 2
	if f == 1:
		print(-1)
	else:
		print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 0
	q = 0
	for i in l:
		if i % 3 == 1:
			p += 1
		elif i % 3 == 2:
			q += 1
		else:
			pass
	o = min(p, q)
	z = abs(p - q)
	if z % 3 == 0:
		k = 2 * (z // 3) + o
		print(k)
	else:
		print('-1')


for i in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 3 != 0:
		print(-1)
	else:
		one = 0
		two = 0
		for b in a:
			if b % 3 == 0:
				pass
			elif b % 3 == 1:
				one = one + 1
			elif b % 3 == 2:
				two = two + 1
		k = min(one, two)
		ans = k
		one = one - k
		two = two - k
		if one == 0:
			ans = ans + int(two / 3) * 2
		else:
			ans = ans + int(one / 3) * 2
		print(ans)


def solve():
	for t in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		mp = [0] * 3
		rem = 0
		for ele in arr:
			c = ele % 3
			rem += c
			mp[c] += 1
		if rem % 3 != 0:
			print(-1)
		else:
			mini = min(mp[1], mp[2])
			mp[1] -= mini
			mp[2] -= mini
			ans = mini
			ans += mp[1] // 3 * 2
			ans += mp[2] // 3 * 2
			print(ans)
solve()


import math
try:
	n = int(input())
	for i in range(1, n + 1):
		A = []
		q = []
		sum = 0
		flag1 = 0
		flag2 = 0
		s = int(input())
		p = list(map(int, input().split()))
		for k in range(len(p)):
			sum += p[k]
			q.append(int(p[k]))
		if sum % 3 != 0:
			print(-1)
		else:
			for o in range(0, len(q)):
				if q[o] % 3 == 1:
					flag1 += 1
				if q[o] % 3 == 2:
					flag2 += 1
			if flag1 == flag2:
				print(flag1)
			elif flag1 > flag2:
				ans = flag2
				ans += (flag1 - flag2) // 3 * 2
				print(ans)
			else:
				ans = flag1
				ans += (flag2 - flag1) // 3 * 2
				print(ans)
except EOFError as e:
	pass


import random
from collections import Counter, defaultdict
from copy import deepcopy as dc
import math
try:
	t = int(input())
	for tt in range(1, t + 1):
		n = int(input())
		a = list(map(int, input().split()))
		x = sum(a)
		if x % 3 != 0:
			print(-1)
		else:
			div0 = 0
			div1 = 0
			div2 = 0
			for i in a:
				if i % 3 == 0:
					div0 += 1
				elif i % 3 == 1:
					div1 += 1
				else:
					div2 += 1
			if div1 == div2:
				print(div1)
			elif div1 > div2:
				ans = div2
				ans += (div1 - div2) // 3 * 2
				print(ans)
			else:
				ans = div1
				ans += (div2 - div1) // 3 * 2
				print(ans)
except EOFError as e:
	pass


from collections import Counter

def _func(a):
	_dict = dict({1: 0, 2: 0})
	_af = [item % 3 for item in a]
	_af = list(filter(lambda num: num != 0, _af))
	_counter = dict(Counter(_af))
	_dict.update(_counter)
	_flagMin = min(_dict[1], _dict[2])
	_flagMax = max(_dict[1], _dict[2])
	if (_flagMax - _flagMin) % 3 == 0:
		return int(_flagMin + (_flagMax - _flagMin) / 3 * 2)
	else:
		return '-1'

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		print(_func(a))
main()


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if sum(A) % 3 != 0:
		print(-1)
	else:
		count = 0
		dict = {0: 0, 1: 0, 2: 0}
		for num in A:
			dict[num % 3] += 1
		temp = min(dict[1], dict[2])
		count += temp
		dict[1] -= temp
		dict[2] -= temp
		val = dict[1] // 3
		count += val * 2
		val = dict[2] // 3
		count += val * 2
		print(count)


for testis in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	l = [i % 3 for i in p]
	o = l.count(1)
	t = l.count(2)
	ans = 0
	m = min(o, t)
	ans = ans + m
	o = o - m
	t = t - m
	ans = ans + o // 3 * 2
	ans = ans + t // 3 * 2
	o = o % 3
	t = t % 3
	if o == 0 and t == 0:
		print(ans)
	else:
		print(-1)


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(ones, twos) = (0, 0)
	for i in range(n):
		arr[i] = arr[i] % 3
		if arr[i] == 1:
			ones += 1
		if arr[i] == 2:
			twos += 1
	if sum(arr) % 3 != 0:
		print(-1)
	else:
		result = min(ones, twos)
		result += int(abs(ones - twos) / 3) * 2
		print(result)


t = int(input())
for i in range(t):
	x = int(input())
	l = [int(n) % 3 for n in input().split()]
	c1 = l.count(1)
	c2 = l.count(2)
	summ = sum(l)
	if summ % 3 != 0:
		print('-1')
	elif x == 1 and l[0] % 3 != 0:
		print('-1')
	elif c1 == 0 and c2 == 0:
		print('0')
	elif c1 == c2:
		print(c1)
	elif c1 > c2:
		if (c1 - c2) % 3 == 0:
			print(c2 + (c1 - c2) // 3 * 2)
	elif c2 > c1:
		if (c2 - c1) % 3 == 0:
			print(c1 + (c2 - c1) // 3 * 2)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	rem1 = len(list(filter(lambda x: x % 3 == 1, lst)))
	rem2 = len(list(filter(lambda x: x % 3 == 2, lst)))
	if rem1 == rem2:
		print(rem2)
		continue
	if abs(rem2 - rem1) % 3 == 0:
		c = abs(rem2 - rem1) // 3
		c *= 2
		mn = min(rem1, rem2)
		print(c + mn)
	else:
		print(-1)


T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	(one, two) = (0, 0)
	for i in arr:
		one += i % 3 == 1
		two += i % 3 == 2
	ops = 0
	ops += min(one, two)
	(one, two) = (one - min(one, two), two - min(one, two))
	ops += one // 3 * 2
	ops += two // 3 * 2
	one %= 3
	two %= 3
	if one == two:
		print(ops + one)
	else:
		print(-1)


def func(N, A):
	d = {}
	d[0] = 0
	d[1] = 0
	d[2] = 0
	for i in range(N):
		rem = A[i] % 3
		d[rem] += 1
	ans = 0
	if (d[0] * 0 + d[1] * 1 + d[2] * 2) % 3 != 0:
		return -1
	else:
		temp = min(d[1], d[2])
		ans += temp
		d[1] -= temp
		d[2] -= temp
		ans = ans + 2 * (d[1] // 3 + d[2] // 3)
		return ans
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(func(N, A))


T = int(input())
if 1 <= T <= 1000:
	for _ in range(T):
		N = int(input())
		if 2 <= N <= pow(10, 5):
			arr = list(map(int, input().split()[:N]))
			c_1 = 0
			c_2 = 0
			for i in range(N):
				arr[i] %= 3
				if arr[i] == 1:
					c_1 += 1
				elif arr[i] == 2:
					c_2 += 1
			arr[:] = (value for value in arr if value != 0)
			if c_1 == c_2:
				print(c_1)
			else:
				if c_1 > c_2:
					temp = c_1 - c_2
					min = c_2
				else:
					temp = c_2 - c_1
					min = c_1
				if temp != 0 and temp % 3 == 0:
					print(min + temp // 3 * 2)
				else:
					print('-1')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c1, c2) = (0, 0)
	for j in range(n):
		if l[j] % 3 == 1:
			c1 += 1
		elif l[j] % 3 == 2:
			c2 += 1
	if (max(c1, c2) - min(c1, c2)) % 3 == 0:
		print(min(c1, c2) + (max(c1, c2) - min(c1, c2)) // 3 * 2)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	rem = {1: 0, 2: 0}
	for i in L:
		if i % 3 == 1:
			rem[1] += 1
		if i % 3 == 2:
			rem[2] += 1
	m = min(rem[1], rem[2])
	M = max(rem[1], rem[2])
	if (2 * rem[2] + rem[1]) % 3 != 0:
		print(-1)
	else:
		print(m + 2 * (M - m) // 3)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	b = []
	for i in range(n):
		if l[i] % 3 != 0:
			if (l[i] + 1) % 3 == 0:
				a.append(l[i])
			elif (l[i] - 1) % 3 == 0:
				b.append(l[i])
	mi = 0
	lena = len(a)
	lenb = len(b)
	mi = mi + min(lena, lenb)
	if lena >= lenb:
		if (lena - lenb) % 3 == 0:
			print(mi + int((lena - lenb) / 3) * 2)
			continue
		else:
			print(-1)
	elif (lenb - lena) % 3 == 0:
		print(mi + int((lenb - lena) / 3) * 2)
		continue
	else:
		print(-1)


x = int(input())
for i in range(x):
	n = int(input())
	a = list(map(int, input().split()))
	plus = 0
	minus = 0
	for h in a:
		if h % 3 == 1:
			minus = minus + 1
		elif h % 3 == 2:
			plus = plus + 1
	d = abs(minus - plus)
	if minus == plus:
		print(plus)
	elif d % 3 == 0:
		m = min(minus, plus)
		y = d // 3
		z = y * 2
		print(m + z)
	else:
		print('-1')


try:
	for _ in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		arr = [0] * 3
		for i in lst:
			arr[i % 3] = arr[i % 3] + 1
		if (arr[1] * 1 + arr[2] * 2) % 3:
			print(-1)
		else:
			ans = 0
			temp = min(arr[1], arr[2])
			arr[1] -= temp
			arr[2] -= temp
			ans += temp
			ans += 2 * (int(arr[1] / 3) + int(arr[2] / 3))
			print(ans)
except:
	pass