Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

A sequence of integers is beautiful if each element of this sequence is divisible by 4.

You are given a sequence a_{1}, a_{2}, ..., a_{n}. In one step, you may choose any two elements of this sequence, remove them from the sequence and append their sum to the sequence. Compute the minimum number of steps necessary to make the given sequence beautiful.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer n.
The second line contains n space-separated integers a_{1}, a_{2}, ..., a_{n}.

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

For each test case, print a single line containing one number — the minimum number of steps necessary to make the given sequence beautiful. If it's impossible to make the sequence beautiful, print -1 instead.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ n ≤ 10^{5}$
$1 ≤ sum of n over all test cases ≤ 10^{6}$
$0 ≤ a_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
1
7
1 2 3 1 2 3 8
----- Sample Output 1 ------ 
3

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
n = int(input())
for i in range(n):
	t = int(input())
	num = list(map(int, input().split(' ')))
	if sum(num) % 4 == 0:
		num = [j % 4 for j in num if j % 4 != 0]
		a1 = num.count(1)
		a2 = num.count(2)
		a3 = num.count(3)
		if a1 == a3:
			ans = a1 + a2 // 2
		elif a1 < a3:
			c3 = a3 - a1
			if c3 % 4 == 0:
				a = c3 // 4 * 3
			elif c3 % 4 == 2:
				a = c3 // 4 * 3 + 2
			ans = a1 + a + a2 // 2
		elif a3 < a1:
			c1 = a1 - a3
			if c1 % 4 == 0:
				a = c1 // 4 * 3
			elif c1 % 4 == 2:
				a = c1 // 4 * 3 + 2
			ans = a3 + a + a2 // 2
		print(ans)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	n = int(input())
	x = y = z = 0
	for i in input().split():
		t = int(i) % 4
		if t == 0:
			pass
		elif t == 1:
			x += 1
		elif t == 2:
			y += 1
		else:
			z += 1
	if (x + 2 * y + 3 * z) % 4:
		print('-1', end='\n')
		continue
	if x + y + z == 0:
		print('0', end='\n')
		continue
	moves = 0
	moves = min(x, z)
	x -= moves
	z -= moves
	moves += y // 2
	y %= 2
	if y == 1:
		if x == 0:
			z -= 2
			moves += 2
		else:
			x -= 2
			moves += 2
		y -= 1
	moves += (x // 4 + z // 4) * 3
	print(moves)


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	l = []
	l1 = []
	for j in s:
		k = int(j)
		l.append(k)
		l1.append(k % 4)
	c3 = l1.count(3)
	c1 = l1.count(1)
	c2 = l1.count(2)
	if c3 == c1 and c2 % 2 == 0:
		print(c3 + c2 // 2)
	elif c3 != c1:
		d = max(c1, c3) - min(c1, c3)
		ans = min(c1, c3)
		if d % 2:
			print(-1)
		elif d // 2 % 2 == c2 % 2:
			if c2 > d // 2:
				ans += d
				c2 -= d // 2
				ans += c2 // 2
				print(ans)
			else:
				ans += 2 * c2
				d -= 2 * c2
				if not d % 4:
					ans += 3 * d // 4
					print(ans)
				else:
					print(-1)
		else:
			print(-1)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	b = [i / 4 - int(i / 4) for i in map(int, input().split()) if i % 4 != 0]
	if sum(b) != int(sum(b)):
		print(-1)
	else:
		a = min(b.count(0.25), b.count(0.75))
		s = max(b.count(0.25), b.count(0.75))
		q = b.count(0.5)
		c = int(q / 2)
		print
		if q % 2 == 1:
			print(int(a + c + 2 + (s - a - 2) * 3 / 4))
		else:
			print(int(a + c + (s - a) * 3 / 4))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(lambda x: int(x) % 4, input().split()))
	c = Counter(a)
	ans = min(c[1], c[3])
	(c[1], c[3]) = (c[1] - ans, c[3] - ans)
	if c[1] % 2 == 1 or c[3] % 2 == 1:
		print(-1)
	else:
		c[2] += c[1] // 2 + c[3] // 2
		ans += c[1] // 2 + c[3] // 2
		if c[2] % 2 == 1:
			print(-1)
		else:
			ans += c[2] // 2
			print(ans)


t = int(input())
for i in range(t):
	length = int(input())
	arr = list(map(int, input().split()))
	count = [0, 0, 0]
	for el in arr:
		if el % 4 != 0:
			count[el % 4 - 1] += 1
	weightedTotal = count[0] * 1 + count[1] * 2 + count[2] * 3
	if weightedTotal % 4 == 0:
		total = count[1] // 2 + min(count[0], count[2])
		count[1] %= 2
		(count[0], count[2]) = (count[0] - min(count[0], count[2]), count[2] - min(count[0], count[2]))
		if count[0] > count[2]:
			total += count[0] // 4 * 3
			count[0] %= 4
		else:
			total += count[2] // 4 * 3
			count[2] %= 4
		if sum(count) > 0:
			total += sum(count) - 1
		print(total)
	else:
		print(-1)


from collections import Counter

def solve():
	n = int(input())
	c = Counter([int(x) % 4 for x in input().split()])
	res = min(c[1], c[3])
	(c[1], c[3]) = (c[1] - res, c[3] - res)
	if c[1] % 2 == 1 or c[3] % 2 == 1:
		print(-1)
	else:
		c[2] += c[1] // 2 + c[3] // 2
		res += c[1] // 2 + c[3] // 2
		if c[2] % 2 == 1:
			print(-1)
		else:
			res += c[2] // 2
			print(res)
t = int(input())
while t:
	solve()
	t -= 1


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	count3 = 0
	summ = 0
	for i in range(n):
		x = arr[i] % 4
		summ += x
		if x == 1:
			count1 += 1
		if x == 2:
			count2 += 1
		if x == 3:
			count3 += 1
	if summ % 4 != 0:
		print(-1)
		continue
	else:
		if count2 == 0 and count1 != 0 and (count3 == 0):
			tt = count1 // 4
			print(3 * tt)
		if count2 == 0 and count1 == 0 and (count3 != 0):
			tt = count3 // 4
			print(3 * tt)
		if count2 % 2 == 0 and count1 == count3:
			print(count2 // 2 + count1)
		flag1 = min(count1, count3)
		flag2 = abs(count1 - count3)
		if count2 % 2 == 0 and count1 != count3:
			flag3 = flag2 // 4
			flag4 = flag3 * 3
			print(count2 // 2 + flag1 + flag4)
		if count2 % 2 != 0 and count1 != count3:
			flag3 = flag2 - 2
			flag4 = flag3 // 4
			flag5 = flag4 * 3
			print((count2 - 1) // 2 + flag1 + flag5 + 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % 4 != 0:
		print(-1)
	else:
		l1 = []
		a1 = 0
		a2 = 0
		a3 = 0
		for i in l:
			if i % 4 != 0:
				l1.append(i % 4)
				if i % 4 == 1:
					a1 += 1
				if i % 4 == 2:
					a2 += 1
				if i % 4 == 3:
					a3 += 1
		if a1 == a3:
			ans = a1 + a2 // 2
		elif a1 < a3:
			c3 = a3 - a1
			if c3 % 4 == 0:
				a = c3 // 4 * 3
			elif c3 % 4 == 2:
				a = c3 // 4 * 3 + 2
			ans = a1 + a + a2 // 2
		elif a3 < a1:
			c1 = a1 - a3
			if c1 % 4 == 0:
				a = c1 // 4 * 3
			elif c1 % 4 == 2:
				a = c1 // 4 * 3 + 2
			ans = a3 + a + a2 // 2
		print(ans)


t = int(input())
for i in range(0, t):
	n = input()
	str1 = input()
	c1 = 0
	c2 = 0
	c3 = 0
	lista = []
	a = ''
	for i in str1:
		if i == ' ':
			lista.append(int(a))
			a = ''
		else:
			a = a + i
	lista.append(int(a))
	for i in lista:
		if i % 4 == 1:
			c1 += 1
		if i % 4 == 2:
			c2 += 1
		if i % 4 == 3:
			c3 += 1
	if (c1 + 2 * c2 + 3 * c3) % 4 != 0:
		print('-1')
	else:
		res = min(c1, c3) + abs(c1 - c3) / 2
		c2 += abs(c1 - c3) / 2
		res = res + c2 / 2
		print(int(res))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = {0: 0, 1: 0, 2: 0, 3: 0}
	s = 0
	for i in range(n):
		a[i] = a[i] % 4
		s += a[i]
		c[a[i]] += 1
	if s % 4 != 0:
		print(-1)
	else:
		rs = 0
		p1 = min(c[1], c[3])
		rs += p1
		c[1] -= p1
		c[3] -= p1
		while c[1] > 0:
			p2 = min(c[1] // 2, c[2])
			c[1] -= p2 * 2
			c[2] -= p2
			rs += p2 * 2
			p3 = c[1] // 4
			rs += p3 * 3
			c[1] -= p3 * 4
		while c[3] > 0:
			p2 = min(c[3] // 2, c[2])
			c[3] -= p2 * 2
			c[2] -= p2
			rs += p2 * 2
			p3 = c[3] // 4
			rs += p3 * 3
			c[3] -= p3 * 4
		while c[2] > 0:
			p4 = c[2] // 2
			rs += p4
			c[2] -= p4 * 2
		print(rs)


t = 0
t = int(input())
while t > 0:
	n = int(input())
	arr = [0, 0, 0, 0]
	sum = 0
	strn = input()
	for x in strn.split():
		number = int(x)
		arr[number % 4] = arr[number % 4] + 1
		sum = (sum + number) % 4
	ans = 0
	if sum % 4 != 0:
		print('-1')
	else:
		if arr[2] % 2 == 0:
			ans = ans + int(arr[2] / 2)
			temp = min(arr[1], arr[3])
			ans = ans + temp
			temp = arr[3] + arr[1] - temp - temp
			temp = int(temp / 4) * 3
			ans = ans + temp
		else:
			temp = int(arr[2] / 2)
			ans = ans + temp
			temp = min(arr[1], arr[3])
			ans = ans + temp
			temp = int(arr[3] + arr[1]) - temp - temp
			ans = ans + 2
			temp = temp - 2
			ans = ans + int(temp / 4) * 3
		print(ans)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(s_1, s_2, s_3) = (0, 0, 0)
	ans = 0
	for i in a:
		if i % 4 == 1:
			s_1 += 1
		elif i % 4 == 2:
			s_2 += 1
		elif i % 4 == 3:
			s_3 += 1
	flag = 0
	ans += min(s_1, s_3)
	x = abs(s_1 - s_3)
	if x & 1:
		print(-1)
	else:
		ans += x // 2
		s_2 += x // 2
		if s_2 & 1:
			print(-1)
		else:
			print(ans + s_2 // 2)


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	num = []
	for i in range(3):
		num.append(0)
	for j in range(n):
		if li[j] % 4 == 1:
			num[0] += 1
		elif li[j] % 4 == 2:
			num[1] += 1
		elif li[j] % 4 == 3:
			num[2] += 1
	ma = max(num[0], num[2])
	mi = min(num[0], num[2])
	if (ma - mi) % 2 == 1:
		print(-1)
	elif ((ma - mi) / 2 + num[1]) % 2 == 1:
		print(-1)
	else:
		print(int(mi + ((ma - mi) / 2 + num[1]) / 2 + (ma - mi) / 2))


t = int(input())
for _ in range(t):
	__ = input()
	as_ = [int(x) % 4 for x in input().split()]
	sum_as = sum(as_) % 4
	if sum_as != 0:
		print(-1)
		continue
	cts = [as_.count(x) for x in range(4)]
	n_min = min(cts[1], cts[3])
	n_remdr = max(cts[1], cts[3]) - n_min
	n_2s = n_remdr // 2 + cts[2]
	print(n_min + n_remdr // 2 + n_2s // 2)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = [int(i.strip()) for i in input().split()]
	if sum(a) % 4 != 0:
		res = -1
	else:
		b = [0 for i in range(4)]
		for i in a:
			b[i % 4] += 1
		res = min(b[1], b[3])
		rem = (max(b[1], b[3]) - res) // 2
		res += rem + (rem + b[2]) // 2
	print(res)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	rem1 = 0
	rem2 = 0
	rem3 = 0
	for i in range(n):
		if a[i] % 4 == 1:
			rem1 += 1
		elif a[i] % 4 == 2:
			rem2 += 1
		elif a[i] % 4 == 3:
			rem3 += 1
	total = rem2 // 2
	if rem1 == rem3:
		total += rem1
		if rem2 % 2 == 1:
			print(-1)
		else:
			print(total)
	elif rem1 > rem3:
		total += rem3
		rem1 = rem1 - rem3
		if rem1 % 2 == 1:
			print(-1)
		elif rem1 % 4 == 0:
			total += rem1 // 4 * 3
			if rem2 % 2 == 1:
				print(-1)
			else:
				print(total)
		else:
			total += rem1 // 4 * 3
			if rem2 % 2 == 1:
				total += 2
				print(total)
			else:
				print(-1)
	else:
		total += rem1
		rem3 = rem3 - rem1
		if rem3 % 2 == 1:
			print(-1)
		elif rem3 % 4 == 0:
			total += rem3 // 4 * 3
			if rem2 % 2 == 1:
				print(-1)
			else:
				print(total)
		else:
			total += rem3 // 4 * 3
			if rem2 % 2 == 1:
				total += 2
				print(total)
			else:
				print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	count1 = 0
	count2 = 0
	count3 = 0
	for j in s:
		if j % 4 == 1:
			count1 += 1
		elif j % 4 == 2:
			count2 += 1
		elif j % 4 == 3:
			count3 += 1
	count = 0
	count += count2 // 2
	count2 = count2 % 2
	a = min(count1, count3)
	count += a
	count1 -= a
	count3 -= a
	sum = count1 + count2 * 2 + count3 * 3
	if sum % 4 != 0:
		print(-1)
	else:
		if count2 == 0:
			count += max(count1, count3) // 4 * 3
		else:
			count += 2
			if count1 > 0 or count3 > 0:
				count += max(count1 - 2, count3 - 2) // 4 * 3
		print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	stack13 = []
	num2 = 0
	ans = 0
	for elem in arr:
		e = elem % 4
		if e == 1 or e == 3:
			if not stack13:
				stack13.append(e)
			elif stack13[-1] == e:
				stack13.append(e)
			else:
				stack13.pop()
				ans += 1
		elif e == 2:
			num2 ^= 1
			if num2 == 0:
				ans += 1
	if (sum(stack13) + 2 * num2) % 4 != 0:
		print(-1)
	elif num2:
		ans += 3 * (len(stack13) - 2) // 4 + 2
		print(ans)
	else:
		ans += 3 * len(stack13) // 4
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 4:
		print('-1')
		continue
	count = [0] * 4
	for x in a:
		count[x % 4] += 1
	ans = count[2] // 2
	if count[1] > count[3]:
		ans += count[3]
		count[1] -= count[3]
		if count[1] > 0:
			if count[2] % 2:
				ans += 2
				count[1] -= 2
			ans += int(count[1] / 4 * 3)
	else:
		ans += count[1]
		count[3] -= count[1]
		if count[3] > 0:
			if count[2] % 2:
				ans += 2
				count[3] -= 2
			ans += int(count[3] / 4 * 3)
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = [-1, 0, 0, 0]
	for i in l:
		if i % 4:
			x[i % 4] += 1
	ans = min(x[1], x[3])
	x[1] -= ans
	x[3] -= ans
	if x[1] % 2 == 1 or x[3] % 2 == 1:
		print(-1)
		continue
	ans += x[1] // 2 + x[3] // 2
	x[2] += x[1] // 2 + x[3] // 2
	if x[2] % 2:
		print(-1)
		continue
	print(ans + x[2] // 2)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	count_arr = [0] * 3
	ans = 0
	possible = True
	for i in arr:
		num = i % 4
		if num:
			count_arr[num - 1] += 1
	one_and_three = min(count_arr[0], count_arr[2])
	count_arr[0] -= one_and_three
	count_arr[2] -= one_and_three
	ans += one_and_three
	two_and_three = min(count_arr[1], count_arr[2] // 2)
	count_arr[1] -= two_and_three
	count_arr[2] -= two_and_three * 2
	ans += two_and_three * 2
	ans += count_arr[1] // 2
	count_arr[1] %= 2
	one_ans_two = min(count_arr[1], count_arr[0] // 2)
	count_arr[1] -= one_ans_two
	count_arr[0] -= one_ans_two * 2
	ans += one_ans_two * 2
	ans += count_arr[0] // 4 * 3
	count_arr[0] %= 4
	if sum(count_arr) != 0:
		possible = False
	if not possible:
		print(-1)
	else:
		print(ans)


from collections import Counter as cc
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = map(lambda x: x % 4, l)
	d = dict(cc(l))
	total = 0
	steps = 0
	if (d[1] + d[2] * 2 + d[3] * 3) % 4 != 0:
		print(-1)
	else:
		steps = min(d[1], d[3])
		total += steps
		d[1] -= steps
		d[3] -= steps
		if d[1] == 0 and d[3] == 0:
			total += d[2] // 2
		elif d[1] == 0 or d[3] == 0:
			d[3] = max(d[1], d[3])
			total += d[2] // 2
			d[2] %= 2
			if d[2] == 0:
				total += d[3] // 4 * 3
			else:
				total += (d[3] - 2) // 4 * 3 + 2
		print(total)


def mgc(count):
	ans = 0
	temp = min(count[1], count[3])
	ans += temp
	count[1] -= temp
	count[3] -= temp
	ans += count[2] // 2
	count[2] = count[2] % 2
	if count[2] == 1:
		if count[1] >= 2:
			count[1] -= 2
			count[2] = 0
			ans += 2
		elif count[3] >= 2:
			count[3] -= 2
			count[2] = 0
			ans += 2
		else:
			return -1
	if count[1] % 4 != 0 or count[3] % 4 != 0:
		return -1
	if count[1] > 0:
		ans += 3 * (count[1] // 4)
	if count[3] > 0:
		ans += 3 * (count[3] // 4)
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = [0, 0, 0, 0]
	for i in arr:
		count[i % 4] += 1
	print(mgc(count))


t = int(input())
while t:
	n = int(input())
	l = [0 for i in range(4)]
	ll = list(map(int, input().split()))
	for val in ll:
		l[val % 4] += 1
	if l[1] == l[3]:
		if l[2] % 2:
			print(-1)
		else:
			print(l[1] + l[2] // 2)
	elif l[1] > l[3]:
		ans = 0
		ans += l[3]
		l[1] -= l[3]
		if l[1] & 1:
			print(-1)
		elif l[1] % 4 == 0 and l[2] % 2 == 0:
			print(l[1] // 4 * 3 + l[2] // 2 + ans)
		elif l[1] % 4 != 0 and l[2] % 2 != 0:
			print((l[1] - 2) // 4 * 3 + (l[2] - 1) // 2 + 2 + ans)
		else:
			print(-1)
	else:
		ans = 0
		ans += l[1]
		l[3] -= l[1]
		if l[3] & 1:
			print(-1)
		elif l[3] % 4 == 0 and l[2] % 2 == 0:
			print(l[3] // 4 * 3 + l[2] // 2 + ans)
		elif l[3] % 4 != 0 and l[2] % 2 != 0:
			print((l[3] - 2) // 4 * 3 + (l[2] - 1) // 2 + 2 + ans)
		else:
			print(-1)
	t -= 1


import math
from functools import reduce
import sys
sys.setrecursionlimit(1000000)

def read(func=str, sep=None):
	return list(map(func, input().split(sep)))

def read_ints(sep=None):
	return read(func=int, sep=sep)

def read_int():
	return int(input())

def print_array(arr, sep=' '):
	print(sep.join(map(str, arr)))

def bitcount(num):
	bits = 0
	while num:
		if num & 1:
			bits += 1
		num >>= 1
	return bits

def highest_bit(n):
	count = 0
	while n != 0:
		count += 1
		n >= 1
	return count - 1

def modpow(num, pow, mod):
	if pow == 0:
		return 1
	c = modpow(num, pow // 2, mod)
	if pow & 1:
		return c ** 2 % mod * num % mod
	else:
		return c ** 2 % mod
ncr_memo = {}

def ncr(n, r):
	if n < r:
		return 0
	if r == 0:
		return 1
	if n == 1:
		return 1
	if r == 1:
		return n
	if (n, r) in ncr_memo:
		return ncr_memo[n, r]
	ncr_memo[n, r] = ncr(n - 1, r) + ncr(n - 1, r - 1)
	return ncr_memo[n, r]
test_cases = read_int()
for _ in range(test_cases):
	n = read_int()
	a = read_ints()
	rem = {1: 0, 2: 0, 3: 0, 0: 0}
	for i in a:
		rem[i % 4] += 1
	turns = 0
	turns += min(rem[1], rem[3])
	rem[1] -= turns
	rem[3] -= turns
	turns += rem[2] // 2
	rem[2] = rem[2] & 1
	turns += 3 * (rem[3] // 4)
	rem[3] %= 4
	turns += 3 * (rem[1] // 4)
	rem[1] %= 4
	m_rem = max(rem[1], rem[3])
	if m_rem == 2 and rem[2] == 1:
		turns += 2
		print(turns)
	elif m_rem == 0 and rem[2] == 0:
		print(turns)
	else:
		print(-1)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	r1 = 0
	r2 = 0
	r3 = 0
	for i in arr:
		if i % 4 == 1:
			r1 += 1
		if i % 4 == 2:
			r2 += 1
		if i % 4 == 3:
			r3 += 1
	if (r1 + r2 * 2 + r3 * 3) % 4 != 0:
		print('-1')
	else:
		count = 0
		mn = min(r1, r3)
		count += mn
		r1 -= mn
		r3 -= mn
		count += r2 // 2
		r2 = r2 % 2
		r = max(r1, r3)
		print(count + r // 4 * 3 + 2 * r2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	r1 = 0
	r2 = 0
	r3 = 0
	for i in arr:
		if i % 4 == 1:
			r1 += 1
		if i % 4 == 2:
			r2 += 1
		if i % 4 == 3:
			r3 += 1
	if (r1 + r2 * 2 + r3 * 3) % 4 != 0:
		print('-1')
	else:
		count = 0
		mn = min(r1, r3)
		count += mn
		r1 -= mn
		r3 -= mn
		count += r2 // 2
		r2 = r2 % 2
		r = max(r1, r3)
		print(count + r // 4 * 3 + 2 * r2)


for _ in range(int(input())):
	t = int(input())
	arr = [int(i) for i in input().split()]
	ra = 0
	rb = 0
	rc = 0
	for i in arr:
		if i % 4 == 1:
			ra += 1
		if i % 4 == 2:
			rb += 1
		if i % 4 == 3:
			rc += 1
	if (ra + rb * 2 + rc * 3) % 4 != 0:
		print('-1')
	else:
		count = 0
		q = min(ra, rc)
		count += q
		ra -= q
		rc -= q
		count += rb // 2
		rb = rb % 2
		if ra == 0:
			count += rc // 4 * 3
			if rb:
				print(count + 2)
			else:
				print(count)
		else:
			count += ra // 4 * 3
			if rb:
				print(count + 2)
			else:
				print(count)


x = int(input())
for i in range(0, x):
	c = 0
	g = input()
	r = list(map(int, input().split()))
	if sum(r) % 4 != 0:
		print(-1)
	else:
		d = [0, 0, 0, 0]
		for i in r:
			d[i % 4] += 1
		c = c + int(d[2] / 2) + min(d[1], d[3])
		d[2] = d[2] % 2
		v = min(d[1], d[3])
		d[1] = d[1] - v
		d[3] = d[3] - v
		if d[1] == 0 and d[3] == 0:
			if d[2] % 2 != 0:
				print(-1)
			else:
				print(c)
		elif d[1] == 0:
			if d[2] == 0:
				c = c + int(d[3] / 4) * 3
				if d[3] % 4 != 0:
					print(-1)
				else:
					print(c)
			elif d[3] >= 2:
				c = c + 2
				d[3] -= 2
				c = c + int(d[3] / 4) * 3
				if d[3] % 4 != 0:
					print(-1)
				else:
					print(c)
			else:
				print(-1)
		else:
			d[3] = d[1]
			if d[2] == 0:
				c = c + int(d[3] / 4) * 3
				if d[3] % 4 != 0:
					print(-1)
				else:
					print(c)
			elif d[3] >= 2:
				c = c + 2
				d[3] -= 2
				c = c + int(d[3] / 4) * 3
				if d[3] % 4 != 0:
					print(-1)
				else:
					print(c)
			else:
				print(-1)


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n):
		A[i] = A[i] % 4
	if sum(A) % 4:
		print(-1)
		continue
	(a1, a2, a3) = (A.count(1), A.count(2), A.count(3))
	(p, q) = (max(a1, a3), min(a1, a3))
	p = p - q
	res = q + p // 4 * 3 + p % 4 + a2 // 2
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	rc = [0] * 4
	for i in range(len(a)):
		rc[a[i] % 4] += 1
	op = 0
	m = min(rc[1], rc[3])
	op += m
	rc[1] -= m
	rc[3] -= m
	op += rc[2] >> 1
	rc[2] %= 2
	if rc[3] > 0:
		rc[2] += rc[3] >> 1
		op += rc[3] >> 1
		rc[3] %= 2
	elif rc[1] > 0:
		rc[2] += rc[1] >> 1
		op += rc[1] >> 1
		rc[1] %= 2
	if rc[3] > 0 or rc[1] > 0:
		print(-1)
	elif rc[2] & 1:
		print(-1)
	else:
		op += rc[2] >> 1
		print(op)


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	d = []
	e = []
	if sum(a) % 4 == 0:
		for i in range(len(a)):
			if a[i] % 2 == 0 and a[i] % 4 != 0:
				b.append(a[i])
			elif a[i] % 4 != 0:
				c.append(a[i])
		t = int(len(b) // 2)
		for i in range(len(c)):
			if c[i] % 4 == 1:
				d.append(c[i])
			elif c[i] % 4 == 3:
				e.append(c[i])
		x = int(min(len(d), len(e)))
		y = int(max(len(d), len(e)))
		if len(b) % 2 == 0:
			if len(d) == len(e):
				z = 0
			else:
				z = (y - x) // 4 * 3
		else:
			z = (y - x - 2) // 4 * 3 + 2
		print(t + x + z)
	else:
		print('-1')


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


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	ans = 0
	q = {1: 0, 2: 0, 3: 0}
	for i in range(n):
		if a[i] % 4:
			q[a[i] % 4] += 1
	o = min(q[1], q[3])
	q[1] -= o
	q[3] -= o
	ans += o
	ans += q[2] // 2
	q[2] %= 2
	k = q[1] + q[3] + 2 * q[2]
	if k % 4 == 0:
		print(ans + q[1] + q[3] + q[2] - k // 4)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	remain = 0
	for i in range(n):
		arr[i] = arr[i] % 4
	(n1, n2, n3) = (arr.count(1), arr.count(2), arr.count(3))
	if sum(arr) % 4:
		print(-1)
		continue
	(ma, mi) = (max(n1, n3), min(n1, n3))
	ma -= mi
	print(mi + ma // 4 * 3 + ma % 4 + n2 // 2)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().strip().split()))
	c = {0: 0, 1: 0, 2: 0, 3: 0}
	for i in range(a):
		c[b[i] % 4] += 1
	c[0] = 0
	ct = 0
	if c[1] > c[3]:
		ct += c[3]
		c[1] -= ct
		c[3] -= ct
		if c[1] % 2 == 1:
			print(-1)
		else:
			c[2] += c[1] // 2
			ct += c[1] // 2
			if c[2] % 2 == 1:
				print(-1)
			else:
				print(ct + c[2] // 2)
	else:
		ct += c[1]
		c[1] -= ct
		c[3] -= ct
		if c[3] % 2 == 1:
			print(-1)
		else:
			c[2] += c[3] // 2
			ct += c[3] // 2
			if c[2] % 2 == 1:
				print(-1)
			else:
				print(ct + c[2] // 2)


t = int(input())
for _ in range(t):
	required_moves = 0
	s = 0
	elements = [0, 0, 0]
	n = int(input())
	l = list(map(int, input().split()))
	for i in l:
		if i % 4 == 1:
			elements[0] += 1
			s += 1
		elif i % 4 == 2:
			elements[1] += 1
			s += 2
		elif i % 4 == 3:
			elements[2] += 1
			s += 3
	if s % 4 != 0:
		print(-1)
		continue
	min_1_3 = min(elements[0], elements[2])
	required_moves += elements[1] // 2 + min_1_3
	elements[0] -= min_1_3
	elements[2] -= min_1_3
	required_moves += 3 * (elements[0] // 4) + 3 * (elements[2] // 4) + elements[0] % 4 + elements[2] % 4
	print(required_moves)


n = int(input())
while n > 0:
	n = n - 1
	x = int(input())
	y = input()
	a = []
	y = y.split(' ')
	y = list(map(lambda z: int(z), y))
	mod_1 = 0
	mod_2 = 0
	mod_3 = 0
	sum = 0
	total_add = 0
	for i in range(0, x):
		sum = sum + y[i]
		rem = y[i] % 4
		if rem == 0:
			continue
		elif rem == 1:
			mod_1 = mod_1 + 1
		elif rem % 4 == 2:
			mod_2 = mod_2 + 1
		else:
			mod_3 = mod_3 + 1
	if sum % 4 != 0:
		print(-1)
		continue
	total_add = min(mod_3, mod_1)
	mod_3 -= total_add
	mod_1 -= total_add
	if mod_2 > 0:
		total_add = total_add + mod_2 / 2
	mod_2 = mod_2 % 2
	if mod_2 == 1:
		if mod_1 > 1:
			mod_1 = mod_1 - 2
		else:
			mod_3 = mod_3 - 2
		total_add = total_add + 2
	if mod_3 > 0:
		total_add = total_add + mod_3 / 4 * 3
	if mod_1 > 0:
		total_add = total_add + mod_1 / 4 * 3
	print(int(total_add))


from math import *
from bisect import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	memo_ = {0: 0, 1: 0, 2: 0, 3: 0}
	for i in a:
		memo_[i % 4] += 1
	steps = min(memo_[1], memo_[3])
	memo_[1] -= steps
	memo_[3] -= steps
	if memo_[1] % 2 or memo_[3] % 2:
		print(-1)
		continue
	memo_[2] += (memo_[1] + memo_[3]) // 2
	steps += (memo_[1] + memo_[3]) // 2
	if memo_[2] % 2:
		print(-1)
		continue
	steps += memo_[2] // 2
	print(steps)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [*map(int, input().split())]
	if sum(a) % 4 != 0:
		print(-1)
	else:
		s = 0
		(o, tw, th, f) = (0, 0, 0, 0)
		for num in a:
			if num % 4 == 1:
				o += 1
			elif num % 4 == 2:
				tw += 1
			elif num % 4 == 3:
				th += 1
			else:
				f += 1
		s += tw // 2
		tw = tw % 2
		while o > 0 and th > 0:
			s += 1
			o -= 1
			th -= 1
		x = max(o, th) // 4
		s += 3 * x
		print(s if tw == 0 else s + 2)


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = [0] * 4
	for i in A:
		B[i % 4] += 1
	C = B[1] + 2 * B[2] + 3 * B[3]
	if C % 4:
		print(-1)
	else:
		val = min(B[1], B[3])
		B[3] -= val
		B[1] -= val
		val += B[2] // 2
		B[2] = B[2] % 2
		if B[2]:
			val += 2
			if B[3]:
				B[3] -= 2
			if B[1]:
				B[1] -= 2
		if B[1]:
			val += B[1] // 4 * 3
		if B[3]:
			val += B[3] // 4 * 3
		print(val)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 4 != 0:
		print(-1)
	else:
		s = [0] * 4
		for i in range(n):
			s[a[i] % 4] += 1
		x = min(s[1], s[3])
		y = abs(s[1] - s[3])
		z = s[2] // 2
		if y == 0:
			z += x
		elif s[2] % 2 == 0:
			z += x + 3 * (y // 4)
		else:
			z += x + 3 * ((y - 2) // 4) + 2
		print(z)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 4 != 0:
		print(-1)
		continue
	s = [0] * 4
	for i in range(n):
		s[a[i] % 4] += 1
	z = s[2] // 2 + min(s[1], s[3]) + 3 * ((abs(s[1] - s[3]) - 2 * (s[2] % 2)) // 4) + 2 * (s[2] % 2)
	print(z)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = [[], [], [], []]
	s = []
	for i in range(4):
		l[i] = [x for x in a if x % 4 == i]
		s.append(len(l[i]))
	if sum(a) % 4 != 0:
		print(-1)
	elif len(l[2]) % 2 == 0:
		extra = max(s[1], s[3]) - min(s[1], s[3])
		print(s[2] // 2 + min(s[1], s[3]) + extra // 4 * 3)
	else:
		extra = max(s[1], s[3]) - min(s[1], s[3]) - 2
		print(s[2] // 2 + min(s[1], s[3]) + extra // 4 * 3 + 2)


T = int(input())
while T:
	T -= 1
	n = int(input())
	A = list(map(int, input().split(' ')))
	r1 = r2 = r3 = 0
	total = 0
	for a in A:
		if a % 4 == 1:
			r1 += 1
		elif a % 4 == 2:
			r2 += 1
		elif a % 4 == 3:
			r3 += 1
		total += a
	if total % 4 != 0:
		print(-1)
	else:
		(pairs13, pairs22) = (min(r1, r3), r2 // 2)
		r1 -= pairs13
		r3 -= pairs13
		left13 = r1 + r3
		ans = pairs13 + pairs22
		if r2 % 2 == 1:
			if left13 >= 2:
				left13 -= 2
				ans += 2
			else:
				print(-1)
		if left13 > 0:
			if left13 % 4 != 0:
				print(-1)
			else:
				ans += 3 * (left13 // 4)
		print(ans)


from math import ceil, log2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 4 != 0:
		print(-1)
		continue
	c = [0, 0, 0, 0]
	step = 0
	for i in a:
		mod = i % 4
		if mod != 0:
			if mod == 1:
				if c[3] > 0:
					c[3] -= 1
					step += 1
				else:
					c[1] += 1
			if mod == 3:
				if c[1] > 0:
					c[1] -= 1
					step += 1
				else:
					c[3] += 1
			if mod == 2:
				if c[2] > 0:
					c[2] -= 1
					step += 1
				else:
					c[2] += 1
	sumc = sum(c)
	if c[1] != 0 or c[3] != 0:
		q = (c[1] + c[3]) // 4
		r = (c[1] + c[3]) % 4
		step += q * 3
	if c[2] != 0:
		step += 2
	print(step)


T = int(input())
for test in range(T):
	N = int(input())
	ll = [int(x) for x in input().split()]
	count = [0 for i in range(4)]
	sum = 0
	for i in range(len(ll)):
		ll[i] = ll[i] % 4
		count[ll[i]] += 1
		sum += ll[i]
	if sum % 4 != 0:
		print(-1)
		continue
	res = 0
	res += count[2] // 2
	count[2] = count[2] % 2
	mi = min(count[1], count[3])
	ma = max(count[1], count[3])
	res += mi
	left = ma - mi
	if count[2] > 0:
		res += 2
		left -= 2
	res += 3 * (left // 4)
	print(res)


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


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] = arr[i] % 4
	dic = {}
	for i in range(n):
		dic[arr[i]] = dic.get(arr[i], 0) + 1
	cnt = 0
	ones = dic.get(1, 0)
	trees = dic.get(3, 0)
	twos = dic.get(2, 0)
	if ones > trees:
		ones -= trees
		cnt += trees
		cnt += twos // 2
		rem_t = twos % 2
		if rem_t <= ones and rem_t > 0:
			if ones >= 2:
				ones -= 2
				cnt += 2
			if ones % 4 == 0:
				cnt += 3 * (ones // 4)
				print(cnt)
			else:
				print(-1)
		elif ones % 4 == 0:
			cnt += 3 * (ones // 4)
			print(cnt)
		else:
			print(-1)
	elif trees > ones:
		trees -= ones
		cnt += ones
		cnt += twos // 2
		rem_t = twos % 2
		ops = trees // 4
		rem_th = trees % 4
		if trees >= rem_t and rem_t > 0:
			if trees >= 2:
				trees -= 2
				cnt += 2
			if trees % 4 == 0:
				cnt += 3 * (trees // 4)
				print(cnt)
			else:
				print(-1)
		elif trees % 4 == 0:
			cnt += 3 * (trees // 4)
			print(cnt)
		else:
			print(-1)
	else:
		cnt += ones
		if twos % 2 == 0:
			cnt += twos // 2
			print(cnt)
		else:
			print(-1)


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


for i in range(int(input())):
	n = int(input())
	d = {1: 0, 2: 0, 3: 0}
	a = [int(i) % 4 for i in input().split()]
	for i in a:
		if i:
			d[i] += 1
	m = min(d[1], d[3])
	moves = m
	d[1] -= m
	d[3] -= m
	temp = d[1] // 2 + d[3] // 2
	d[1] = d[1] & 1
	d[3] = d[3] & 1
	moves += temp
	temp += d[2]
	if temp & 1 or d[1] or d[3]:
		print(-1)
	else:
		print(moves + temp // 2)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	countArr = [0] * 4
	for i in l:
		countArr[i % 4] += 1
	if (countArr[1] + 2 * countArr[2] + 3 * countArr[3]) % 4 != 0:
		print(-1)
	else:
		count = 0
		count += min(countArr[1], countArr[3])
		countArr[1] -= count
		countArr[3] -= count
		count += countArr[2] // 2
		countArr[2] = countArr[2] % 2
		if countArr[1] == 0 and countArr[3] == 0:
			print(count)
		else:
			temp = countArr[1] + countArr[3]
			if countArr[2] > 0 and temp > 1:
				count += 2
				temp -= 2
				countArr[2] -= 1
			if temp > 0:
				count += 3 * temp // 4
			print(count)
t = int(input())
while t:
	solve()
	t -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	s = sum(L)
	if s % 4 != 0:
		print(-1)
	else:
		M = {0: 0, 1: 0, 2: 0, 3: 0}
		for i in range(n):
			M[L[i] % 4] += 1
		a = M[1]
		b = M[2]
		c = M[3]
		if a == c:
			print(a + b // 2)
		elif a > c:
			ans = c
			a -= c
			ans += b // 2
			if b % 2 == 0:
				b = 0
			else:
				b = 1
			ans += a // 2
			a = a // 2 + b
			ans += a // 2
			print(ans)
		else:
			ans = a
			c -= a
			ans += b // 2
			if b % 2 == 0:
				b = 0
			else:
				b = 1
			ans += c // 2
			c = c // 2 + b
			ans += c // 2
			print(ans)


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import math, heapq, bisect
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	ans = 0
	arr = [a[i] % 4 for i in range(n) if a[i] % 4]
	even = [num for num in arr if not num & 1]
	ans += len(even) // 2
	rem_even = len(even) % 2
	odd = [num for num in arr if num & 1]
	d = Counter(odd)
	mini = min(d[1], d[3])
	ans += mini
	rem_odd = len(odd) - mini * 2
	if not rem_even:
		if rem_odd % 4:
			print(-1)
		else:
			ans += rem_odd // 4 * 3
			print(ans)
	elif rem_odd < 2:
		print(-1)
	else:
		rem_odd -= 2
		ans += 2
		if rem_odd % 4:
			print(-1)
		else:
			ans += rem_odd // 4 * 3
			print(ans)


def mgc(arr):
	if sum(arr) % 4 != 0:
		return -1
	remainder_map = [0, 0, 0, 0]
	for i in arr:
		remainder = i % 4
		remainder_map[remainder] += 1
	ans = 0
	first_try = min(remainder_map[1], remainder_map[3])
	ans += first_try
	remainder_map[1] -= first_try
	remainder_map[3] -= first_try
	second_try = remainder_map[2] // 2
	ans += second_try
	remainder_map[2] %= 2
	if remainder_map[1] > 0:
		remainder_map[2] += remainder_map[1] // 2
		ans += remainder_map[1] // 2
	if remainder_map[3] > 0:
		remainder_map[2] += remainder_map[3] // 2
		ans += remainder_map[3] // 2
	return ans + remainder_map[2] // 2
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(mgc(arr))


n = int(input())
for i in range(0, n):
	k = int(input())
	arr = list(map(int, input().split(' ')))
	for j in range(0, k):
		arr[j] = arr[j] % 4
	cnt = 0
	a1 = arr.count(1)
	a2 = arr.count(2)
	a3 = arr.count(3)
	cnt = cnt + min(a1, a3)
	cnt = cnt + a2 // 2
	if a2 % 2 == 1:
		if abs(a3 - a1) >= 2:
			cnt = cnt + 2
			if (abs(a3 - a1) - 2) % 4 == 0:
				cnt = cnt + (abs(a3 - a1) - 2) // 4 * 3
				print(cnt)
			else:
				print(-1)
		else:
			print(-1)
	elif abs(a3 - a1) % 4 == 0:
		cnt = cnt + abs(a3 - a1) * 3 // 4
		print(cnt)
	else:
		print(-1)