Chef has an array A of length N.

In one operation, Chef can:
Choose any two distinct indices i, j (1≤ i, j≤ N) and change both A_{i} and A_{j} to (A_{i} + A_{j}). Note that both the elements A_{i} and A_{j} are getting replaced by the same value.

Find the minimum number of operations required by Chef to make all the elements divisible by 3.

It is guaranteed that we can make all the elements divisible by 3 using some finite number of operations.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N - denoting the length of array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots A_{N}.

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

For each test case, output the minimum number of operations required by Chef to make all the elements divisible by 3.

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

$1 ≤ T ≤ 1000$
$4 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4
4 8 20 16
4
4 3 6 9

----- Sample Output 1 ------ 
2
6

----- explanation 1 ------ 
Test case $1$: We can make all the elements divisible by $3$ using $2$ operations.
- Operation $1$: Choose $i = 1$ and $j = 2$. Thus, we replace both $A_{1}$ and $A_{2}$ by $A_{1}+A_{2} = 4+8 = 12$. The array becomes $[12, 12, 20, 16]$.
- Operation $2$: Choose $i = 3$ and $j = 4$. Thus, we replace both $A_{3}$ and $A_{4}$ by $A_{3}+A_{4} = 20+16 = 36$. The array becomes $[12, 12, 36, 36]$.

All elements of the array are divisible by $3$. It can be shown that this is the minimum number of operations required to do so.

Test case $2$: We can make all the elements divisible by $3$ using $6$ operations.
- Operation $1$: Choose $i = 1$ and $j = 2$. Thus, we replace both $A_{1}$ and $A_{2}$ by $A_{1}+A_{2} = 4+3 = 7$. The array becomes $[7, 7, 6, 9]$.
- Operation $2$: Choose $i = 1$ and $j = 3$. Thus, we replace both $A_{1}$ and $A_{3}$ by $A_{1}+A_{3} = 7+6 = 13$. The array becomes $[13, 7, 13, 9]$.
- Operation $3$: Choose $i = 1$ and $j = 2$. Thus, we replace both $A_{1}$ and $A_{2}$ by $A_{1}+A_{2} = 13+7 = 20$. The array becomes $[20, 20, 13, 9]$.
- Operation $4$: Choose $i = 3$ and $j = 4$. Thus, we replace both $A_{3}$ and $A_{4}$ by $A_{3}+A_{4} = 13+9 = 22$. The array becomes $[20, 20, 22, 22]$.
- Operation $5$: Choose $i = 1$ and $j = 3$. Thus, we replace both $A_{1}$ and $A_{3}$ by $A_{1}+A_{3} = 20+22= 42$. The array becomes $[42, 20, 42, 22]$.
- Operation $6$: Choose $i = 2$ and $j = 4$. Thus, we replace both $A_{2}$ and $A_{4}$ by $A_{2}+A_{4} = 20+22= 42$. The array becomes $[42, 42, 42, 42]$.

All elements of the array are divisible by $3$. It can be shown that this is the minimum number of operations required to do so.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
tests = int(input())
while tests:
	tests -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	(c0, c1, c2) = (0, 0, 0)
	for x in arr:
		if x % 3 == 0:
			c0 += 1
		elif x % 3 == 1:
			c1 += 1
		else:
			c2 += 1
	diff = abs(c1 - c2)
	if c2 > c1:
		(c2, c1) = (c1, c2)
	res = 0
	if diff == 0:
		res = c1
	elif diff == 1:
		if c2 == 0:
			res = 6
		else:
			res = c1 + 1
	elif diff == 2:
		if c2 == 0:
			res = 5
		elif c2 > 1:
			res = c1 + 2
		elif c2 == 1:
			if c0 == 0:
				res = 6
			else:
				res = 5
	elif diff == 3:
		res = c1 + 1
	elif diff == 4:
		res = c2 + 3
	else:
		res = (diff // 4 - 1) * 3
		diff = diff % 4
		res += c2 + 1
		if diff == 0:
			res += 2
		elif diff == 1:
			res += 4
		elif diff == 2:
			res += 6
		elif diff == 3:
			res += 6
	print(res)


for i in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]
	ones = 0
	twos = 0
	for i in range(len(arr)):
		if arr[i] % 3 == 1:
			ones += 1
		elif arr[i] % 3 == 2:
			twos += 1
	(x, y) = (min(ones, twos), max(ones, twos))
	count = 0
	while y - x > 2:
		y -= 2
		x += 2
		count += 1
	if abs(x - y) == 0:
		print(x + count)
	elif abs(x - y) == 1:
		if min(x, y) != 0:
			print(count + min(x, y) + 2)
		else:
			print(count + 6)
	elif min(x, y) == 0:
		print(count + 5)
	elif len(arr) == 4:
		print(count + 6)
	else:
		print(max(x, y) - 3 + count + 5)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = [x % 3 for x in [*map(int, input().split())]]
	(x, y) = (ar.count(1), ar.count(2))
	(x, y) = (min(x, y), max(x, y))
	res = 0
	while y >= x + 3:
		res += 1
		x += 2
		y -= 2
	(x, y) = (min(x, y), max(x, y))
	if y == x + 1:
		res += 2 if x else 6
	if y == x + 2:
		res += 4 if x > 1 or (x > 0 and x + y < n) else 5
	print(res + x)


def solve(n, arr):
	n0 = 0
	n1 = 0
	n2 = 0
	for i in range(n):
		if arr[i] % 3 == 1:
			n1 += 1
		elif arr[i] % 3 == 2:
			n2 += 1
		else:
			n0 += 1
	if n1 > n2:
		temp = n2
		n2 = n1
		n1 = temp
	counter = 0
	while n2 - n1 > 2:
		n2 -= 2
		n1 += 2
		counter += 1
	if n1 > n2:
		temp = n2
		n2 = n1
		n1 = temp
	counter += n1
	if n2 - n1 == 1:
		if n1 == 1 and n0 != 0 or n1 > 1:
			counter += 2
		else:
			counter += 6
	elif n2 - n1 == 2:
		if n1 == 1 and n0 != 0 or n1 > 1:
			counter += 4
		else:
			counter += 5
	print(counter)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	solve(n, a)


for _ in range(int(input())):
	n = int(input())
	a = [x % 3 for x in [*map(int, input().split())]]
	(x, y) = (a.count(1), a.count(2))
	(x, y) = (min(x, y), max(x, y))
	ans = 0
	while y >= x + 3:
		ans += 1
		x += 2
		y -= 2
	(x, y) = (min(x, y), max(x, y))
	if y == x + 1:
		ans += 2 if x else 6
	if y == x + 2:
		ans += 4 if x > 1 or (x > 0 and x + y < n) else 5
	print(ans + x)


test = int(input())
for t in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] %= 3
	x = a.count(1)
	y = a.count(2)
	(x, y) = (min(x, y), max(x, y))
	ans = 0
	while y >= x + 3:
		ans += 1
		x += 2
		y -= 2
	(x, y) = (min(x, y), max(x, y))
	if y == x + 1:
		if x > 0:
			ans += 2
		else:
			ans += 6
	if y == x + 2:
		if x > 1 or (x > 0 and x + y < n):
			ans += 4
		else:
			ans += 5
	print(ans + x)


from bisect import bisect_left
from bisect import bisect_right
from getopt import getopt
import re
from tempfile import tempdir
from traceback import print_tb
from typing import DefaultDict
import math
from collections import Counter, defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import copy
import heapq
from collections import deque
import sys

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans

def ncr_modulo(n, r, p):
	num = 2
	den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return l

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

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

def modInverse(b, m):
	return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def solve(t):
	n = int(input())
	d = defaultdict(lambda : 0)
	l = list(map(int, input().split()))
	ans = 0
	for ele in l:
		d[ele % 3] += 1
	while abs(d[1] - d[2]) > 2:
		if d[1] < d[2]:
			d[2] -= 2
			d[1] += 2
		else:
			d[1] -= 2
			d[2] += 2
		ans += 1
	k = min(d[1], d[2])
	x = max(d[1], d[2])
	diff = x - k
	if diff == 0:
		return ans + k
	elif diff == 2:
		if k == 0:
			return ans + 5
		elif k == 1:
			if d[0] >= 1:
				return ans + 5
			return ans + 6
		return ans + x + 2
	else:
		if k == 0:
			return ans + 6
		return ans + x + 1
for t in range(1, int(input()) + 1):
	print(solve(t))


zor = int(input())
di = {}

def ite(l):
	r = []
	for u in l:
		for a in range(3):
			for b in range(a, 3):
				if u[a] and u[b] and (a != b or u[a] >= 2):
					uc = list(u)
					uc[(a + b) % 3] += 2
					uc[a] -= 1
					uc[b] -= 1
					v = tuple(uc)
					if not v in vu:
						r.append(v)
						vu.add(v)
	return r
ex = (3, 1, 0)
for n0 in range(8):
	for n1 in range(8):
		for n2 in range(8):
			if n0 + n1 + n2 >= 4:
				ini = tuple([n0, n1, n2])
				l = [ini]
				vu = {l[0]}
				t = 0
				while min(((n1 - n2) % 4 for (n0, n1, n2) in l)):
					l = ite(l)
					t += 1
				di[ini] = t + min((abs(n1 - n2) // 4 + (n1 + n2) // 2 for (n0, n1, n2) in l if n1 % 4 == n2 % 4))
				l = ite(l)
				if l and min(((n1 - n2) % 4 for (n0, n1, n2) in l)) == 0:
					di[ini] = min(di[ini], t + 1 + min((abs(n1 - n2) // 4 + (n1 + n2) // 2 for (n0, n1, n2) in l if n1 % 4 == n2 % 4)))

def redu(n):
	if n >= 4:
		return n % 4 + 4
	return n
for zo in range(zor):
	n = int(input())
	A = list(map(int, input().split()))
	N = [0, 0, 0]
	for k in A:
		N[k % 3] += 1
	Nn = [redu(k) for k in N]
	s = abs(N[2] - Nn[2] - N[1] + Nn[1]) // 4
	s += (N[2] - Nn[2]) // 2
	s += (N[1] - Nn[1]) // 2
	print(s + di[Nn[0], Nn[1], Nn[2]])