Monocarp is playing a computer game. He's going to kill $n$ monsters, the $i$-th of them has $h_i$ health.

Monocarp's character has two spells, either of which he can cast an arbitrary number of times (possibly, zero) and in an arbitrary order:

choose exactly two alive monsters and decrease their health by $1$;

choose a single monster and kill it.

When a monster's health becomes $0$, it dies.

What's the minimum number of spell casts Monocarp should perform in order to kill all monsters?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 100$) — the number of monsters.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 100$) — the health of each monster.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^4$.


-----Output-----

For each testcase, print a single integer — the minimum number of spell casts Monocarp should perform in order to kill all monsters.


-----Examples-----

Input
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5
Output
3
3
5


-----Note-----

In the first testcase, the initial health list is $[1, 2, 1, 2]$. Three spells are casted:

the first spell on monsters $1$ and $2$ — monster $1$ dies, monster $2$ has now health $1$, new health list is $[0, 1, 1, 2]$;

the first spell on monsters $3$ and $4$ — monster $3$ dies, monster $4$ has now health $1$, new health list is $[0, 1, 0, 1]$;

the first spell on monsters $2$ and $4$ — both monsters $2$ and $4$ die.

In the second testcase, the initial health list is $[2, 4, 2]$. Three spells are casted:

the first spell on monsters $1$ and $3$ — both monsters have health $1$ now, new health list is $[1, 4, 1]$;

the second spell on monster $2$ — monster $2$ dies, new health list is $[1, 0, 1]$;

the first spell on monsters $1$ and $3$ — both monsters $1$ and $3$ die.

In the third testcase, the initial health list is $[1, 2, 3, 4, 5]$. Five spells are casted. The $i$-th of them kills the $i$-th monster with the second spell. Health list sequence: $[1, 2, 3, 4, 5]$ $\rightarrow$ $[0, 2, 3, 4, 5]$ $\rightarrow$ $[0, 0, 3, 4, 5]$ $\rightarrow$ $[0, 0, 0, 4, 5]$ $\rightarrow$ $[0, 0, 0, 0, 5]$ $\rightarrow$ $[0, 0, 0, 0, 0]$.

Difficulty: EASY
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	print(len((a := s.split())) - a.count('1') // 2)


for s in [*open(0)][2::2]:
	print(len((x := s.split())) - x.count('1') // 2)


for k in [*open(0)][2::2]:
	print(len((a := k.split())) - a.count('1') // 2)


import sys
input = sys.stdin.readline
out = []
for _ in range(int(input())):
	n = int(input())
	h = [int(i) for i in input().split()]
	ans = h.count(1)
	out.append(ans // 2 + n - ans // 2 * 2)
for i in out:
	print(i)


for s1 in [*open(0)][2::2]:
	print(len((a := s1.split())) - a.count('1') // 2)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	L = [*map(int, input().split())]
	L.sort()
	oneCount = L.count(1) // 2
	return len(L) - oneCount
T = int(input())
for i in range(T):
	print(solve())


import sys
N = int(sys.stdin.readline())
for i in range(N):
	M = int(sys.stdin.readline())
	arvud = sys.stdin.readline().split()
	i_arv = arvud.count('1')
	tul = len(arvud)
	if i_arv == 0:
		print(tul)
	elif i_arv % 2 == 0:
		tul = tul - i_arv + i_arv / 2
		print(int(tul))
	else:
		tul = tul - i_arv + i_arv / 2 + 1
		print(int(tul))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	x = a.count(1)
	print((x + 1) // 2 + n - x)
t = int(input())
for _ in range(t):
	solve()


import sys
put = sys.stdin.readline
t = int(put())
while t:
	t -= 1
	n = int(put())
	h = list(map(int, put().split()))
	cnt = h.count(1)
	h = len(h) - cnt
	print(h + cnt // 2 + 1 if cnt % 2 else h + cnt // 2)


n = int(input())
l = []
j = 0
for _ in range(n):
	k = input()
	l.append(input())
while j < n:
	k = l[j].split(' ')
	s1 = 0
	s2 = 0
	s3 = 0
	for i in k:
		if i == '1':
			s1 += 1
		elif i == '2':
			s2 += 1
		else:
			s3 += 1
	s1 = s1 - int(s1 / 2)
	print(s1 + s2 + s3)
	j += 1


import sys
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())
t = inp()
for i in range(t):
	n = inp()
	nlist = inlt()
	b = []
	out = 0
	for i in range(n):
		if nlist[i] == 1:
			b.append(i)
	if len(b) % 2 == 0:
		out = n - len(b) / 2
	else:
		out = n - len(b) / 2 + 0.5
	print(int(out))


t = int(input())
res = []
while t > 0:
	n = int(input())
	h = input().split(' ')
	number_of_ones = h.count('1')
	if number_of_ones == len(h):
		if len(h) % 2 == 0:
			res.append(number_of_ones // 2)
		else:
			res.append(number_of_ones // 2 + 1)
	elif number_of_ones > 1:
		if number_of_ones % 2 == 0:
			res.append(len(h) - number_of_ones + number_of_ones // 2)
		else:
			res.append(len(h) - number_of_ones + number_of_ones // 2 + 1)
	else:
		res.append(len(h))
	t -= 1
for element in res:
	print(element)


import math
k = int(input())
res = []
while k > 0:
	n = input()
	temp = input().split(' ')
	arr = []
	for num in temp:
		arr.append(int(num))
	total = 0
	ones = 0
	for num in arr:
		if num == 1:
			ones += 1
	total = len(arr) - ones + math.ceil(ones / 2)
	res.append(total)
	k -= 1
for x in res:
	print(x)


import sys
n = int(sys.stdin.readline())
for i in range(n):
	k = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	count = 0
	count2 = 0
	for j in range(k):
		if l[j] > 1:
			count += 1
		else:
			count2 += 1
			if count2 > 1:
				count2 = 0
				count += 1
	print(count + count2)


import sys
for _ in range(int(sys.stdin.readline().strip())):
	m = int(sys.stdin.readline().strip())
	count1 = 0
	for temp in map(int, sys.stdin.readline().strip().split()):
		if temp == 1:
			count1 += 1
	print(m - count1 + (count1 + 1) // 2)


from sys import stdin, stdout
from math import gcd
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	if len(set(nums)) == 1 and nums[0] == 1:
		print(n - n // 2)
	else:
		nums.sort()
		count = 0
		i = 0
		while i <= n - 1:
			if i == n - 1:
				count += 1
				break
			elif i == n - 2:
				count += 2
				break
			else:
				k = nums[i]
				if k >= 2:
					count += 2
					i += 2
				else:
					count += k
					nums[i + 1] -= k
					if nums[i + 1] == 0:
						i += 2
					else:
						i += 1
		print(count)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = a.count(1) // 2
	print(x + n - x * 2)


n = int(input())
a = [0 for i in range(n)]
for i in range(n):
	li_len = int(input())
	count = li_len
	li = list(map(int, input().split()))
	count -= li.count(1) // 2
	a[i] = count
for i in range(n):
	print(a[i])


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	l = [int(k) for k in inps()]
	l.sort()
	c = 0
	for i in l:
		if i == 1:
			c += 1
	print(math.ceil(c / 2) + n - c)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

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

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


from sys import stdin

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

def readInt():
	return int(readLine())

def readInts():
	return list(map(int, readLine().split()))
(T, N) = (0, 0)

def main():
	T = readInt()
	for i in range(T):
		N = readInt()
		ans = N
		A = readInts()
		A.sort()
		if A[0] == 1:
			j = 1
			while j < N:
				if A[j] == 1:
					ans -= 1
				j += 2
		print(ans)
main()


t = int(input())
l = []
for i in range(t):
	n = int(input())
	ch = input()
	a = ch.split()
	ar = [int(x) for x in a]
	l.append(ar)
for i in range(t):
	ar = l[i]
	un = ar.count(1)
	n = un // 2
	n += len(ar) - un + un % 2
	print(n)


a = int(input())
r = []
for i in range(a):
	c = 0
	n = int(input())
	l = list(map(int, input().split()))
	la = len(l)
	a = l.count(1)
	if a % 2 == 0:
		c += a // 2
		la -= a
	else:
		c += a // 2
		la -= a - 1
	c += la
	r.append(c)
for i in r:
	print(i)


def main():
	n = int(input())
	results = []
	for _ in range(n):
		_ = input()
		healths = list(map(int, input().split()))
		health1_count = healths.count(1)
		results.append(health1_count // 2 + int(health1_count % 2) + (len(healths) - health1_count))
	for r in results:
		print(r)
main()


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

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

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	cnt = sum([i == 1 for i in arr])
	return n - cnt + (cnt + 1) // 2
for _ in range(int(input())):
	print(solve())


def solve():
	t = int(input())
	battles = [[]] * t
	moves = [0] * t
	for i in range(t):
		input()
		battle = list(map(int, input().split()))
		battle.sort()
		battles[i] = battle
	for i in range(t):
		moves[i] = len(battles[i])
		one_hp_monsters = battles[i].count(1)
		if one_hp_monsters > 1:
			moves[i] += one_hp_monsters // 2 - one_hp_monsters + one_hp_monsters % 2
	print('\n'.join(list(map(str, moves))))
solve()


trials = int(input())
answer_list = []
for _ in range(trials):
	i = int(input())
	lis = input().split(' ')
	answer = 0
	var = lis.count('1')
	if var % 2 == 0:
		ans = var / 2 + (i - var)
	else:
		ans = var // 2 + 1 + (i - var)
	answer_list.append(int(ans))
for g in answer_list:
	print(g)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	p = ls.count(1)
	print(n - p + int((p + 1) / 2))


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if len(arr) == 1:
		print(1)
		continue
	c = 0
	for i in range(N - 1):
		if arr[i] == 0:
			continue
		if arr[i] == 1:
			arr[i] -= 1
			arr[i + 1] -= 1
			c += 1
		else:
			arr[i] = 0
			c += 1
	if arr[-1] != 0:
		c += 1
	print(c)


t = int(input())
arr = []
for i in range(t):
	n = int(input())
	nowl = list(map(int, input().split()))
	arr.append(len(nowl) - nowl.count(1) // 2)
for i in arr:
	print(i)


import sys
from math import *
from collections import defaultdict, deque
input = sys.stdin.readline
mod = 10 ** 9 + 7
INF = 1061109567
N = int(2 * 10 ** 5 + 5)
LINF = 4557430888798830399

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if a[i] == 1:
			cnt = cnt + 1
	print(n - int(cnt / 2))
T = int(input())
for t in range(T):
	solve()


T = int(input())
ans = []
for i in range(T):
	n = int(input())
	H = input().split()
	h = []
	for j in H:
		j = int(j)
		h.append(j)
	H = h
	health_1 = []
	health_not1 = []
	for i in H:
		if i == 1:
			health_1.append(i)
		elif i > 1:
			health_not1.append(i)
	if len(health_1) % 2 == 0:
		ans.append(len(health_1) // 2 + len(health_not1))
	else:
		ans.append(len(health_1) // 2 + 1 + len(health_not1))
for i in ans:
	print(i)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	a.sort()
	result = 0
	n = 0
	for (number, i) in enumerate(a):
		if i == 1:
			n += 1
			result += 1
		elif n >= i and i < 3:
			n -= i
		else:
			result += len(a) - number
			break
	print(result - n // 2)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	nlist = list(map(int, input().split()))
	b = []
	out = 0
	for i in range(n):
		if nlist[i] == 1:
			b.append(i)
	if len(b) % 2 == 0:
		out = n - len(b) / 2
	else:
		out = n - len(b) / 2 + 0.5
	print(int(out))


def foo(ls):
	ls.sort()
	count = 0
	ones = 0
	for i in range(len(ls)):
		if ls[i] == 1:
			ones += 1
	rem = len(ls) - ones
	if ones % 2 == 0:
		count = int(ones // 2) + rem
	else:
		count = int(ones // 2) + 1 + rem
	print(count)
n = int(input())
w = []
for _ in range(n):
	x = int(input())
	w.append(list(map(int, input().split())))
for ele in w:
	foo(ele)


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

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

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

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize
from math import ceil

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		ones = 0
		for i in range(n):
			if arr[i] == 1:
				ones += 1
		get_print_int(min(n, n - ones + ceil(ones / 2)))
solve()


import sys

def read_input():
	return int(sys.stdin.readline())

def read_multiple_input():
	return list(map(int, sys.stdin.readline().split()))
t = read_input()
for _ in range(t):
	n = read_input()
	h = read_multiple_input()
	s = sum((1 for health in h if health > 1))
	k = len([health for health in h if health == 1])
	s += (k + 1) // 2
	print(s)


b = []
x = int(input())
for i in range(x):
	y = int(input())
	c = input()
	l = c.split()
	a = l.count('1')
	if a == 0:
		b.append(int(y))
	elif a % 2 == 0:
		b.append(int(y - a / 2))
	else:
		b.append(int(y - a + a // 2 + 1))
for i in range(x):
	print(b[i])


t = int(input())
ls = []
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	a = lst.count(1) // 2
	ls.append(n - a)
for i in range(t):
	print(ls[i])


import sys
if sys.platform == 'ios':
	import clipboard
	a = clipboard.get()
	a = a.split('\n')
	text = '\n'.join(a)
	with open('input_file.txt', 'w') as f:
		f.write(text)
	sys.stdin = open('input_file.txt')
sys.setrecursionlimit(4100000)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
t = ni()
for _ in range(t):
	N = ni()
	A = na()
	res = 0
	cnt = 0
	for i in range(N):
		if A[i] <= 2:
			res += A[i]
			cnt += 1
	ans = (res + 1) // 2 + (N - cnt)
	print(ans)


import math
n = input()
Output = []
for i in range(int(n)):
	k = int(input())
	arr = input().split()
	ones = 0
	for i in arr:
		ones += int(i) == 1
	Output.append(len(arr) - ones + ones // 2 + ones % 2)
for i in Output:
	print(i)


import math
t = int(input())
answerList = list()
for i in range(t):
	n = int(input())
	test = list(map(int, input().split()))
	numOnes = int(0)
	fullHits = int(0)
	for x in range(n):
		if test[x] == 1:
			numOnes += 1
		if test[x] > 1:
			fullHits += 1
	numOnes = math.ceil(numOnes / 2)
	answer = numOnes + fullHits
	answerList.append(answer)
[print(i) for i in answerList]


y = int(input())
h = []
for i in range(y):
	u = int(input())
	p = sorted([int(o) for o in input().split()])[::-1]
	hh = 0
	for uu in range(9999):
		try:
			if p[0] == 1 and p[1] == 1:
				p.pop(0)
				p.pop(1)
				hh += 1
			else:
				p.pop(0)
				hh += 1
		except:
			hh += len(p)
			break
	h.append(hh)
print(*h, sep='\n')


t = int(input())
hl = []
rl = []
for i in range(t):
	n = int(input())
	hl = [int(x) for x in input().split()]
	cs = 0
	c1 = 0
	p = 0
	for j in range(n):
		if hl[j] == 1:
			c1 += 1
	if c1 == 1 or c1 == 0:
		cs = n
	elif c1 % 2 != 0:
		p = c1 // 2
		cs = n - c1 + p + 1
	else:
		p = c1 // 2
		cs = n - c1 + p
	rl.append(cs)
for i in range(t):
	print(rl[i])


n1 = int(input())
ans = []
for i in range(1, n1 + 1):
	n2 = int(input())
	ll = list(map(int, input().strip().split()))[:n2]
	ll.sort()
	c = 0
	for j in range(n2):
		if j == n2 - 1:
			if ll[j] == 0:
				break
			else:
				c += 1
				break
		elif ll[j] == 1:
			ll[j] -= 1
			ll[j + 1] -= 1
			c += 1
		elif ll[j] == 0:
			continue
		else:
			c += 1
	ans.append(c)
for k in ans:
	print(k, end='\n')


import sys, heapq, itertools
from copy import copy, deepcopy
from collections import deque, namedtuple
from itertools import *
from math import *
from random import *
from functools import reduce, lru_cache
sys.setrecursionlimit(10 ** 9)

def main():
	(INF, LLINF) = (10 ** 9, 4 * 10 ** 18)
	(MOD, MOD_EDU) = (10 ** 9 + 7, 998244353)
	ID_FCT = lambda x: x
	input = lambda : sys.stdin.readline().rstrip()
	cache = lru_cache(maxsize=None)

	def modul(n, mod=MOD):
		return (n % mod + mod) % mod

	def err_print(*args, end='\n', sep=' '):
		sys.stderr.write(' '.join(chain([str(a) for a in args], [end])))

	def list_map(string, fct=int):
		return list(map(fct, string.split()))

	def read_matrix(n, f=ID_FCT):
		return [list(map(f, sys.stdin.readline().strip().split())) for _ in range(n)]

	def read_char_matrix(n):
		return [sys.stdin.readline().strip() for _ in range(n)]
	for t in range(int(sys.stdin.readline())):
		n = int(sys.stdin.readline())
		l = list(map(int, sys.stdin.readline().split()))
		n1 = sum((x for x in l if x == 1)) // 2
		print(n - n1)
main()


userInput = []
n = 0
while True:
	if n == 0:
		limit = input()
	elif n == int(limit) * 2 + 1:
		break
	else:
		userInput.append(input())
	n += 1
for i in range(int(limit)):
	length = int(userInput[i * 2])
	string = userInput[i * 2 + 1].split()
	string = sorted([int(x) for x in string])
	num_of_1s = 0
	for j in string:
		if j == 1:
			num_of_1s += 1
	length -= int(num_of_1s)
	length += num_of_1s / 2
	if num_of_1s % 2 == 1:
		length += 1
	print(int(length))


def minspells(lst, index):
	if len(lst) > 1 and lst[0] == 1 and (lst[1] == 1):
		(hd, nxt, tl) = (lst[0], lst[1], lst[2:])
		return minspells(tl, index + 1)
	else:
		return len(lst) + index
N = int(input(''))
main = []
for i in range(1, N + 1):
	n = int(input(''))
	h = str(input(''))
	life = list(map(int, h.split()))
	life.sort()
	main.append(life)
for j in range(0, N):
	print(minspells(main[j], 0))


def no_of_spells(list):
	a = []
	for i in range(0, len(list)):
		if list[i] == 1:
			a.append(1)
		else:
			continue
	return len(list) - len(a) + len(a) // 2 + len(a) % 2
n = int(input())
k = []
for i in range(n):
	temp1 = input()
	temp2 = input()
	lst = map(int, temp2.split())
	k.append(no_of_spells(list(lst)))
for j in range(0, len(k)):
	print(k[j])


t = int(input())
i = 0
I = []
while i < t:
	n = int(input())
	inp = list(map(int, input().split()))
	I.append(inp)
	i += 1
i = 0
while i < t:
	inp = I[i]
	count = 0
	inp.sort()
	if len(inp) % 2 == 1:
		count += 1
		inp.pop()
	for j in range(len(inp) // 2):
		if inp[2 * j] + inp[2 * j + 1] == 1 or inp[2 * j] + inp[2 * j + 1] == 2:
			count += 1
		else:
			count += 2
	print(count)
	i += 1


testcase = int(input(''))
i = 0
lst = []

def Minspellcast(healthlst):
	count_1 = 0
	for k in range(len(healthlst)):
		if healthlst[k] == 1:
			count_1 += 1
	count_rest = n - count_1
	if count_1 % 2 == 0:
		min_spellcast = count_1 // 2 + count_rest
	else:
		min_spellcast = count_1 // 2 + count_rest + 1
	return min_spellcast
while i < testcase:
	n = int(input(''))
	health = input('')
	health_list = health.split()
	for j in range(len(health_list)):
		health_list[j] = int(health_list[j])
	lst.append(Minspellcast(health_list))
	i += 1
for i in range(len(lst)):
	print(lst[i])


t = int(input())
ans1 = []
for i in range(t):
	k = 0
	sum = 0
	n = int(input())
	l = list(map(int, input().split()))
	lst = []
	for i in l:
		if i == 1:
			k += 1
	if k % 2 == 0:
		sum = sum + k / 2
	else:
		sum = sum + k / 2 + 1
	sum = sum + (n - k)
	ans1.append(int(sum))
for i in range(t):
	print(ans1[i])


import math
t = int(input())
A = []
for i in range(t):
	n = int(input())
	a = [int(p) for p in input().split()]
	A.append(a)
for i in range(t):
	arr = A[i]
	lol = [y for y in arr if y == 1]
	lmao = len(arr) - len(lol)
	print(len(lol) // 2 + len(lol) % 2 + lmao)


a = int(input())
for i in range(a):
	n = 0
	b = int(input())
	c = list(map(int, input().split(' ')))
	k = c.count(1)
	if k > 1:
		p = b - k
		if k % 2 == 0:
			n += k / 2
		else:
			n += k // 2 + 1
		print(int(p + n))
	else:
		print(b)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	arr = []
	arr = list(map(int, input().split()))
	mp = {}
	for j in arr:
		if mp.get(j, 0) == 0:
			mp[j] = 1
		else:
			mp[j] += 1
	tot = 0
	tot += mp.get(1, 0) // 2
	tot += len(arr) - mp.get(1, 0) // 2 * 2
	ans.append(tot)
[print(i) for i in ans]


n = int(input())
for _ in range(n):
	t = int(input())
	l = list(input().split())
	cnt = 0
	for single in l:
		if single == '1':
			cnt += 1
	print(t - cnt + (cnt + 1) // 2)


for i in range(int(input())):
	print(int(input()) - list(map(int, input().split())).count(1) // 2)


for _ in range(int(input())):
	nm = int(input())
	c = input().split().count('1') // 2
	print(nm - c)


for _ in range(int(input())):
	n = int(input())
	x = input().split().count('1') // 2
	print(n - x)


for i in range(int(input())):
	(n, ones) = (int(input()), input().split().count('1'))
	print(n - ones // 2)


for kadfk in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(n - a.count(1) // 2)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	ans1 = 0
	ans2 = 0
	for i in input().split():
		if i == '1':
			ans2 += 1
		else:
			ans1 += 1
	print(ans1 + ceil(ans2 / 2))


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	c1 = a.count(1)
	print(c1 // 2 + (n - c1) + c1 % 2)


import math
for _ in range(int(input())):
	input()
	x = input().split()
	count = math.ceil(x.count('1') / 2)
	print(len(x) - x.count('1') + count)


t = int(input())
while t:
	t -= 1
	a = int(input())
	b = [int(i) for i in input().split()]
	ans = b.count(1) // 2 + b.count(1) % 2
	als = a - b.count(1)
	print(ans + als)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	x = a.count(1) // 2
	print(x + n - x * 2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i == 1:
			c += 1
	print(n - c // 2)


def main():
	t = int(input())
	for _ in range(t):
		res = alg()
		print(res)

def alg():
	n = int(input())
	h = [int(x) for x in input().split()]
	h.sort()
	res = 0
	ind = 0
	while ind < n and h[ind] == 1:
		ind += 1
	res += int((ind + 1) / 2) + n - ind
	return res
main()


for test in range(int(input())):
	size = int(input())
	a = list(map(int, input().split()))
	if a.count(1) != size:
		print((a.count(1) + 1) // 2 + size - a.count(1))
	else:
		print((a.count(1) + 1) // 2)