Alice and Bob play a game on an array of N integers. They alternate moves, with Alice making the first move.

The rules are as follows:
1. On their first move, a player can pick any element in the array, add its value to their score, and then remove it from the array.
2. On a move that is not their first move, the player should pick an element with the opposite [parity] of the element chosen on their previous move, add its value to their score, and then remove it from the array.
3. If a player cannot make a move, either because the array is empty or it doesn't contain an element of the parity they need, the player skips their turn.
4. The game ends when both players are unable to move.

Note that the parity of an element chosen by a player depends only on the parity of their own previously chosen element — it does not depend on what their opponent last chose.

Determine the optimal score of Alice if both players play optimally, each attempting to maximize their own score. If there are multiple ways to obtain maximum score for themselves, the players will adopt a strategy that will maximize the score of their opponent whilst obtaining their maximum score themselves. 

Note that it is not necessary to use all the elements in the array.

Also note that when a player skips a turn, the parity that he needs in the next move remains same as that of the current move.

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

- The first line of input will contain a single integer T, denoting the number of test cases. Then the test cases follow.
- Each test case consists of two lines of input.
- The first line of each test case contains one integer N — the size of the array A
- The second line of each test case contains N space-separated integers, denoting the array elements.

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

For each test case, output on a new line the optimal score achieved by Alice.

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

$1 ≤ T ≤ 2\cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ Ai ≤ 10^{6}$
- Sum of $N$ across all test cases won't exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
4
1 2 3 4
3
45 10 53
6
7 5 2 2 6 2
----- Sample Output 1 ------ 
5
55
15
----- explanation 1 ------ 
Test case $1$: Under optimal play, Alice's maximum score is $5$. One sequence of moves leading to this score is:
- On her first move, Alice picks $4$.
- On his first move, Bob picks $3$.
- On her second move, Alice must choose an *odd* number, since she previously picked an even number. So, Alice's only choice is to pick $1$.
- On his second move, Bob picks $2$, since he must choose an *even* number and it is the only one left.

Alice's score is thus $4 + 1 = 5$. Note that this is not the only optimal strategy — however, any other strategy where both players play optimally will still lead to Alice having a score of $5$.

Test case $2$: Alice's strategy is as follows:
- On her first move, Alice picks $10$.
- On his first move, Bob picks $53$.
- Finally, Alice picks $45$, ending up with a score of $10 + 45 = 55$.

Note that if Alice picks either $53$ or $45$ on her first move, Bob will pick $10$ on his move. This leaves Alice unable to make a move, so she skips her turn and Bob picks the remaining number, leaving Alice with a score strictly smaller than $55$.

Test case $3$: Alice picks $6, 7,$ and $2$ for a score of $15$, while Bob picks $2, 5,$ and $2$ for a score of $9$. Note that Bob can also achieve a score of $9$ by picking $7$ and $2$ and then skipping his third move, but he won't do this because it would lead to Alice only reaching a score of $13$ — as mentioned earlier, a player attempts to maximize their own score, and then maximize their opponent's score.

Difficulty: VERY_HARD
Tags: Mathematics

Starter code:

Solutions:
for tcase in range(int(input())):
	n = int(input())
	s = [[], []]
	for si in map(int, input().split()):
		s[si % 2].append(si)
	s[0].sort()
	s[1].sort()
	r = [[[0, 0], [0, 0]], [[0, 0], [0, 0]]]
	for ia in range(2):
		for ib in range(2):
			(a, b, c) = ([], [], [s[0][:], s[1][:]])
			(ap, bp) = (ia, ib)
			if len(c[ap]) > 0:
				a.append(c[ap].pop())
				ap ^= 1
			if len(c[bp]) > 0:
				b.append(c[bp].pop())
				bp ^= 1
			if len(a) > 0 or len(b) > 0:
				while len(c[ap]) > 0 or len(c[bp]) > 0:
					if len(c[ap]) > 0:
						a.append(c[ap].pop())
						ap ^= 1
					if len(c[bp]) > 0:
						b.append(c[bp].pop())
						bp ^= 1
			(r[ia][ib][0], r[ia][ib][1]) = (sum(a), sum(b))
	ascore = [0, 0]
	for ap in range(2):
		d = r[ap][0][1] - r[ap][1][1]
		if d == 0:
			d = r[ap][0][0] - r[ap][1][0]
		bp = 0 if d > 0 else 1
		ascore[ap] = r[ap][bp][0]
	ans = max(ascore)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	line = input()
	a = list(map(int, line.split()))
	a.sort(reverse=True)
	evens = []
	odds = []
	for item in a:
		if item % 2 == 0:
			evens.append(item)
		else:
			odds.append(item)
	Alice_Socres = []
	Bob_Scores_Aeven = []
	Bob_Scores_Aodd = []
	for i in range(4):
		bin_i = bin(i)[2:]
		if i < 2:
			bin_i = '0' + bin_i
		Alice = 0
		Bob = 0
		Alice_even = bin_i[0] == '0'
		Bob_even = bin_i[1] == '0'
		is_Alice_turn = True
		Alice_no_moves = False
		Bob_no_moves = False
		odds_copy = odds.copy()
		evens_copy = evens.copy()
		while True:
			if is_Alice_turn:
				if Alice_even:
					if len(evens_copy) == 0:
						if Bob_no_moves:
							break
						else:
							Alice_no_moves = True
					else:
						Alice += evens_copy.pop(0)
						Alice_even = False
				elif len(odds_copy) == 0:
					if Alice_no_moves:
						break
					else:
						Bob_no_moves = True
				else:
					Alice += odds_copy.pop(0)
					Alice_even = True
			elif Bob_even:
				if len(evens_copy) == 0:
					break
				else:
					Bob += evens_copy.pop(0)
					Bob_even = False
			elif len(odds_copy) == 0:
				break
			else:
				Bob += odds_copy.pop(0)
				Bob_even = True
			is_Alice_turn = not is_Alice_turn
		Alice_Socres.append(Alice)
		if i < 2:
			Bob_Scores_Aeven.append(Bob)
		else:
			Bob_Scores_Aodd.append(Bob)
	if Bob_Scores_Aodd[0] > Bob_Scores_Aodd[1]:
		Alice_Socres.pop(3)
	elif Bob_Scores_Aodd[0] < Bob_Scores_Aodd[1]:
		Alice_Socres.pop(2)
	elif Alice_Socres[2] < Alice_Socres[3]:
		Alice_Socres.pop(2)
	else:
		Alice_Socres.pop(3)
	if Bob_Scores_Aeven[0] > Bob_Scores_Aeven[1]:
		Alice_Socres.pop(1)
	elif Bob_Scores_Aeven[0] < Bob_Scores_Aeven[1]:
		Alice_Socres.pop(0)
	elif Alice_Socres[0] < Alice_Socres[1]:
		Alice_Socres.pop(0)
	else:
		Alice_Socres.pop(1)
	print(max(Alice_Socres))


def get_ans(a, b, arr, A, B):
	n = len(arr)
	d = {0: [], 1: []}
	for i in range(n):
		if arr[i] % 2:
			d[1].append(arr[i])
		else:
			d[0].append(arr[i])
	d[0].sort()
	d[1].sort()
	curr = 'a'
	ap = len(d[a]) > 0
	bp = len(d[b]) > 0
	while ap or bp:
		if curr == 'a':
			if not ap:
				curr = 'b'
				continue
			else:
				A += d[a].pop()
				a = 1 - a
				curr = 'b'
		elif not bp:
			curr = 'a'
			continue
		else:
			B += d[b].pop()
			b = 1 - b
			curr = 'a'
		ap = len(d[a]) > 0
		bp = len(d[b]) > 0
	return (A, B)
for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	mo = [float('-inf'), float('-inf')]
	me = [float('-inf'), float('-inf')]
	for i in range(n):
		if A[i] % 2:
			if A[i] > mo[0]:
				mo[1] = mo[0]
				mo[0] = A[i]
			elif A[i] > mo[1]:
				mo[1] = A[i]
		elif A[i] > me[0]:
			me[1] = me[0]
			me[0] = A[i]
		elif A[i] > me[1]:
			me[1] = A[i]
	ret = []
	ans = []
	if me[0] > float('-inf') and me[1] > float('-inf'):
		arr = A[:]
		arr.remove(me[0])
		arr.remove(me[1])
		ans.append(get_ans(1, 1, arr, me[0], me[1]))
	if me[0] > float('-inf') and mo[0] > float('-inf'):
		arr = A[:]
		arr.remove(me[0])
		arr.remove(mo[0])
		ans.append(get_ans(1, 0, arr, me[0], mo[0]))
	if len(ans) == 2:
		(p1, p2) = ans
		if p1[1] == p2[1]:
			if p1[0] > p2[0]:
				ans = [p1]
			else:
				ans = [p2]
		elif p1[1] > p2[1]:
			ans = [p1]
		else:
			ans = [p2]
	if ans:
		ret.append(ans[0])
	ans = []
	if mo[0] > float('-inf') and me[0] > float('-inf'):
		arr = A[:]
		arr.remove(me[0])
		arr.remove(mo[0])
		ans.append(get_ans(0, 1, arr, mo[0], me[0]))
	if mo[0] > float('-inf') and mo[1] > float('-inf'):
		arr = A[:]
		arr.remove(mo[0])
		arr.remove(mo[1])
		ans.append(get_ans(0, 0, arr, mo[0], mo[1]))
	if len(ans) == 2:
		(p1, p2) = ans
		if p1[1] == p2[1]:
			if p1[0] > p2[0]:
				ans = [p1]
			else:
				ans = [p2]
		elif p1[1] > p2[1]:
			ans = [p1]
		else:
			ans = [p2]
	if ans:
		ret.append(ans[0])
	if len(ret) == 1:
		print(ret[0][0])
	else:
		print(ret[0][0] if ret[0][0] >= ret[1][0] else ret[1][0])


def play(odd_arr, even_arr, sel):
	alice_playing = True
	bob_playing = True
	both_pos = [0, 0]
	both_arr = [odd_arr, even_arr]
	(alice_sel, bob_sel) = sel
	alice_score = 0
	bob_score = 0
	while alice_playing or bob_playing:
		if alice_playing:
			if both_pos[alice_sel] < len(both_arr[alice_sel]):
				alice_score += both_arr[alice_sel][both_pos[alice_sel]]
				both_pos[alice_sel] += 1
				alice_sel = int(alice_sel ^ 1)
			else:
				alice_playing = False
		if bob_playing:
			if both_pos[bob_sel] < len(both_arr[bob_sel]):
				bob_score += both_arr[bob_sel][both_pos[bob_sel]]
				both_pos[bob_sel] += 1
				bob_sel = int(bob_sel ^ 1)
			else:
				bob_playing = False
	return (alice_score, bob_score)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odds = []
	evens = []
	for i in a:
		if i & 1:
			odds.append(i)
		else:
			evens.append(i)
	odds = sorted(odds, reverse=True)
	evens = sorted(evens, reverse=True)
	all_vals = [play(odds, evens, [1, 0]), play(odds, evens, [1, 1]), play(odds, evens, [0, 0]), play(odds, evens, [0, 1])]
	pos_alice = [i[0] for i in all_vals]
	pos_bob = [i[1] for i in all_vals]
	actual_alice = [0, 0]
	if pos_bob[0] > pos_bob[1]:
		actual_alice[0] = pos_alice[0]
	elif pos_bob[1] > pos_bob[0]:
		actual_alice[0] = pos_alice[1]
	else:
		actual_alice[0] = max(pos_alice[:2])
	if pos_bob[2] > pos_bob[3]:
		actual_alice[1] = pos_alice[2]
	elif pos_bob[3] > pos_bob[2]:
		actual_alice[1] = pos_alice[3]
	else:
		actual_alice[1] = max(pos_alice[2:])
	print(max(actual_alice))


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for e in arr:
		if e & 1:
			odd.append(e)
		else:
			even.append(e)
	even.sort(key=lambda x: -x)
	odd.sort(key=lambda x: -x)
	(a1, b1) = (0, 0)
	i = 0
	while i < len(even):
		a1 += even[i]
		if i < len(odd):
			a1 += odd[i]
		else:
			break
		i += 2
	i = 1
	while i < len(even):
		b1 += even[i]
		if i < len(odd):
			b1 += odd[i]
		else:
			break
		i += 2
	(a2, b2) = (0, 0)
	i = 0
	while i < len(even):
		a2 += even[i]
		if i + 1 < len(odd):
			a2 += odd[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(odd):
		b2 += odd[i]
		if i + 1 < len(even):
			b2 += even[i + 1]
		else:
			break
		i += 2
	(a3, b3) = (0, 0)
	i = 0
	while i < len(even):
		b3 += even[i]
		if i + 1 < len(odd):
			b3 += odd[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(odd):
		a3 += odd[i]
		if i + 1 < len(even):
			a3 += even[i + 1]
		else:
			break
		i += 2
	(a4, b4) = (0, 0)
	i = 0
	while i < len(odd):
		a4 += odd[i]
		if i < len(even):
			a4 += even[i]
		else:
			break
		i += 2
	i = 1
	while i < len(odd):
		b4 += odd[i]
		if i < len(even):
			b4 += even[i]
		else:
			break
		i += 2
	ans1 = 0
	b = max(b1, b2)
	if b == b1 == b2:
		ans1 = max(a1, a2)
	elif b == b1:
		ans1 = a1
	else:
		ans1 = a2
	ans2 = 0
	b = max(b3, b4)
	if b == b3 == b4:
		ans2 = max(a3, a4)
	elif b == b3:
		ans2 = a3
	else:
		ans2 = a4
	print(max(ans1, ans2))


def get(arr, a, b):
	choices = [[], []]
	choices[0] = list(filter(lambda x: x % 2 == 0, arr))
	choices[1] = list(filter(lambda x: x % 2 == 1, arr))
	score_a = 0
	score_b = 0
	while True:
		if len(choices[a]) == 0 and len(choices[b]) == 0:
			break
		if len(choices[a]) != 0:
			score_a += choices[a].pop()
			a = 1 - a
		if len(choices[b]) != 0:
			score_b += choices[b].pop()
			b = 1 - b
	return [score_a, score_b]

def get_z(arr, a):
	sc1 = get(arr, a, 0)
	sc2 = get(arr, a, 1)
	if sc1[1] == sc2[1]:
		return max(sc1[0], sc2[0])
	elif sc1[1] > sc2[1]:
		return sc1[0]
	return sc2[0]

def func(arr):
	return max(get_z(arr, 0), get_z(arr, 1))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	print(func(arr))


def func(xx, yy):
	(od, ev) = ([], [])
	for i in tt:
		if i % 2:
			od.append(i)
		else:
			ev.append(i)
	od.sort()
	ev.sort()
	s = [0, 0]
	(a, b) = (0, 0)
	while sum(s) < 2:
		if xx:
			if len(od):
				a += od.pop()
			else:
				s[0] = 1
		elif len(ev):
			a += ev.pop()
		else:
			s[0] = 1
		if yy:
			if len(od):
				b += od.pop()
			else:
				s[1] = 1
		elif len(ev):
			b += ev.pop()
		else:
			s[1] = 1
		if not s[0]:
			xx ^= 1
		if not s[1]:
			yy ^= 1
	return (b, a)
for _ in range(int(input())):
	n = int(input())
	tt = [int(x) for x in input().split()]
	(p, q) = (len([i for i in tt if i % 2]), len([i for i in tt if i % 2 == 0]))
	(x, y) = ([], [])
	x.append(func(0, 0))
	x.append(func(0, 1))
	y.append(func(1, 0))
	y.append(func(1, 1))
	x.sort(reverse=True)
	y.sort(reverse=True)
	print(max(x[0][1], y[0][1]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	eve = []
	odd = []
	for i in l:
		if i % 2 == 0:
			eve.append(i)
		else:
			odd.append(i)
	eve.sort(reverse=True)
	odd.sort(reverse=True)

	def out(la, lb, i, j):
		flag = 0
		if la == 0 and i >= len(eve):
			flag += 1
		elif la == 1 and j >= len(odd):
			flag += 1
		if lb == 0 and i >= len(eve):
			flag += 1
		elif lb == 1 and j >= len(odd):
			flag += 1
		return flag < 2

	def sol(la, lb):
		i = 0
		j = 0
		a = 0
		b = 0
		while out(la, lb, i, j):
			if la == 0:
				if i < len(eve):
					a += eve[i]
					la ^= 1
					i += 1
			elif j < len(odd):
				a += odd[j]
				la ^= 1
				j += 1
			if lb == 0:
				if i < len(eve):
					b += eve[i]
					lb ^= 1
					i += 1
			elif j < len(odd):
				b += odd[j]
				lb ^= 1
				j += 1
		return (a, b)
	(a1, b1) = sol(0, 0)
	(a2, b2) = sol(0, 1)
	(a3, b3) = sol(1, 0)
	(a4, b4) = sol(1, 1)
	ans1 = 0
	if b2 > b1:
		ans1 = a2
	elif b2 == b1:
		ans1 = max(a1, a2)
	else:
		ans1 = a1
	ans2 = 0
	if b4 > b3:
		ans2 = a4
	elif b4 == b3:
		ans2 = max(a3, a4)
	else:
		ans2 = a3
	print(max(ans1, ans2))


t = int(input())

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def get_bns(b, c, x, y):
	bindi = 0
	cindi = 0
	fl = 0
	al = 0
	bob = 0
	bl = 0
	bbl = 0
	cbl = 0
	while (bindi < len(b) or cindi < len(c)) and bl < 2:
		if fl == 0:
			if bbl == 0:
				if x == 0:
					if bindi < len(b):
						al += b[bindi]
						bindi += 1
						x = 1
					else:
						bl += 1
						bbl = 1
				elif cindi < len(c):
					al += c[cindi]
					cindi += 1
					x = 0
				else:
					bl += 1
					bbl = 1
			fl = 1
		else:
			if cbl == 0:
				if y == 0:
					if bindi < len(b):
						bob += b[bindi]
						bindi += 1
						y = 1
					else:
						bl += 1
						cbl = 1
				elif cindi < len(c):
					bob += c[cindi]
					cindi += 1
					y = 0
				else:
					bl += 1
					cbl = 1
			fl = 0
	return (al, bob)
while t > 0:
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	b = []
	c = []
	for i in range(n):
		if a[i] % 2:
			b.append(a[i])
		else:
			c.append(a[i])
	b.sort()
	b = b[::-1]
	c.sort()
	c = c[::-1]
	ansi = [[(0, 0), (0, 0)], [(0, 0), (0, 0)]]
	for i in range(2):
		for j in range(2):
			ansi[i][j] = get_bns(b, c, i, j)
	if ansi[0][0][1] > ansi[0][1][1]:
		po = ansi[0][0][0]
	elif ansi[0][0][1] < ansi[0][1][1]:
		po = ansi[0][1][0]
	else:
		po = max(ansi[0][0][0], ansi[0][1][0])
	if ansi[1][0][1] > ansi[1][1][1]:
		qo = ansi[1][0][0]
	elif ansi[1][0][1] < ansi[1][1][1]:
		qo = ansi[1][1][0]
	else:
		qo = max(ansi[1][0][0], ansi[1][1][0])
	print(max(po, qo))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for el in arr:
		if el % 2:
			odd.append(el)
		else:
			even.append(el)
	odd.sort()
	even.sort()

	def solve(i, j, p, q):
		a = True
		t1 = i
		t2 = j
		b = True
		o = 0
		l = 0
		while a or b:
			if a:
				if t1 % 2:
					if p:
						o += p.pop()
						t1 += 1
					else:
						a = False
				elif q:
					o += q.pop()
					t1 += 1
				else:
					a = False
			if b:
				if t2 % 2:
					if p:
						l += p.pop()
						t2 += 1
					else:
						b = False
				elif q:
					l += q.pop()
					t2 += 1
				else:
					b = False
		return (o, l)
	res = 0
	p = 0
	for i in range(2):
		temp = []
		for j in range(2):
			(a, b) = solve(i, j, odd[:], even[:])
			temp.append([a, b])
		temp.sort(key=lambda x: (-x[1], -x[0]))
		res = max(res, temp[0][0])
	print(res)


t = int(input())

def get_ans(b, c, x, y):
	bind = 0
	cind = 0
	fl = 0
	al = 0
	bob = 0
	bl = 0
	bbl = 0
	cbl = 0
	while (bind < len(b) or cind < len(c)) and bl < 2:
		if fl == 0:
			if bbl == 0:
				if x == 0:
					if bind < len(b):
						al += b[bind]
						bind += 1
						x = 1
					else:
						bl += 1
						bbl = 1
				elif cind < len(c):
					al += c[cind]
					cind += 1
					x = 0
				else:
					bl += 1
					bbl = 1
			fl = 1
		else:
			if cbl == 0:
				if y == 0:
					if bind < len(b):
						bob += b[bind]
						bind += 1
						y = 1
					else:
						bl += 1
						cbl = 1
				elif cind < len(c):
					bob += c[cind]
					cind += 1
					y = 0
				else:
					bl += 1
					cbl = 1
			fl = 0
	return (al, bob)
while t > 0:
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	b = []
	c = []
	for i in range(n):
		if a[i] % 2:
			b.append(a[i])
		else:
			c.append(a[i])
	b.sort()
	b = b[::-1]
	c.sort()
	c = c[::-1]
	ans = [[(0, 0), (0, 0)], [(0, 0), (0, 0)]]
	for i in range(2):
		for j in range(2):
			ans[i][j] = get_ans(b, c, i, j)
	if ans[0][0][1] > ans[0][1][1]:
		p = ans[0][0][0]
	elif ans[0][0][1] < ans[0][1][1]:
		p = ans[0][1][0]
	else:
		p = max(ans[0][0][0], ans[0][1][0])
	if ans[1][0][1] > ans[1][1][1]:
		q = ans[1][0][0]
	elif ans[1][0][1] < ans[1][1][1]:
		q = ans[1][1][0]
	else:
		q = max(ans[1][0][0], ans[1][1][0])
	print(max(p, q))
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for x in a:
		if x % 2 == 0:
			even.append(x)
		else:
			odd.append(x)
	even.sort(reverse=True)
	odd.sort(reverse=True)
	(a1, b1) = (0, 0)
	i = 0
	while i < len(even):
		a1 += even[i]
		if i < len(odd):
			a1 += odd[i]
		else:
			break
		i = i + 2
	i = 1
	while i < len(even):
		b1 += even[i]
		if i < len(odd):
			b1 += odd[i]
		else:
			break
		i += 2
	(a2, b2) = (0, 0)
	i = 0
	while i < len(even):
		a2 += even[i]
		if i + 1 < len(odd):
			a2 += odd[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(odd):
		b2 += odd[i]
		if i + 1 < len(even):
			b2 += even[i + 1]
		else:
			break
		i += 2
	(a3, b3) = (0, 0)
	i = 0
	while i < len(odd):
		a3 += odd[i]
		if i + 1 < len(even):
			a3 += even[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(even):
		b3 += even[i]
		if i + 1 < len(odd):
			b3 += odd[i + 1]
		else:
			break
		i += 2
	(a4, b4) = (0, 0)
	i = 0
	while i < len(odd):
		a4 += odd[i]
		if i < len(even):
			a4 += even[i]
		else:
			break
		i += 2
	i = 1
	while i < len(odd):
		b4 += odd[i]
		if i < len(even):
			b4 += even[i]
		else:
			break
		i += 2
	(ans1, ans2) = (0, 0)
	b = max(b1, b2)
	if b == b1 and b == b2:
		ans1 = max(a1, a2)
	elif b == b1:
		ans1 = a1
	else:
		ans1 = a2
	b = max(b3, b4)
	if b == b3 and b == b4:
		ans2 = max(a3, a4)
	elif b == b3:
		ans2 = a3
	else:
		ans2 = a4
	print(max(ans1, ans2))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = []
	e = []
	for q in l:
		if q % 2 == 0:
			e.append(q)
		else:
			o.append(q)
	e.sort(reverse=True)
	o.sort(reverse=True)
	a1 = 0
	b1 = 0
	i = 0
	while i < len(e):
		a1 = a1 + e[i]
		if i < len(o):
			a1 = a1 + o[i]
		else:
			break
		i += 2
	i = 1
	while i < len(e):
		b1 = b1 + e[i]
		if i < len(o):
			b1 = b1 + o[i]
		else:
			break
		i += 2
	a2 = 0
	b2 = 0
	i = 0
	while i < len(o):
		a2 = a2 + o[i]
		if i < len(e):
			a2 = a2 + e[i]
		else:
			break
		i += 2
	i = 1
	while i < len(o):
		b2 = b2 + o[i]
		if i < len(e):
			b2 = b2 + e[i]
		else:
			break
		i += 2
	a3 = 0
	b3 = 0
	i = 0
	while i < len(o):
		a3 = a3 + o[i]
		if i + 1 < len(e):
			a3 = a3 + e[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(e):
		b3 = b3 + e[i]
		if i + 1 < len(o):
			b3 = b3 + o[i + 1]
		else:
			break
		i += 2
	a4 = 0
	b4 = 0
	i = 0
	while i < len(e):
		a4 = a4 + e[i]
		if i + 1 < len(o):
			a4 = a4 + o[i + 1]
		else:
			break
		i += 2
	i = 0
	while i < len(o):
		b4 = b4 + o[i]
		if i + 1 < len(e):
			b4 = b4 + e[i + 1]
		else:
			break
		i += 2
	ans1 = 0
	b = max(b1, b4)
	if b == b1 == b4:
		ans1 = max(a1, a4)
	elif b == b1:
		ans1 = a1
	else:
		ans1 = a4
	ans2 = 0
	bb = max(b2, b3)
	if bb == b2 == b3:
		ans2 = max(a2, a3)
	elif bb == b2:
		ans2 = a2
	else:
		ans2 = a3
	ans = max(ans1, ans2)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pt = [[], []]
	for i in a:
		if i & 1:
			pt[1].append(i)
		else:
			pt[0].append(i)
	pt[0] = sorted(pt[0], reverse=True)
	pt[1] = sorted(pt[1], reverse=True)
	ans = []
	for test in range(4):
		(flag, tr) = (0, 0)
		par = [test >> 1 & 1, test & 1]
		count = [0, 0]
		ln = [len(pt[0]), len(pt[1])]
		inc = [0, 0]
		while flag < 2:
			if inc[par[tr]] < ln[par[tr]]:
				flag = 0
				count[tr] += pt[par[tr]][inc[par[tr]]]
				inc[par[tr]] += 1
				par[tr] ^= 1
			else:
				flag += 1
			tr ^= 1
		ans.append(count)
	if ans[0][1] > ans[1][1]:
		zero = ans[0][0]
	elif ans[0][1] < ans[1][1]:
		zero = ans[1][0]
	else:
		zero = max(ans[0][0], ans[1][0])
	if ans[2][1] > ans[3][1]:
		one = ans[2][0]
	elif ans[2][1] < ans[3][1]:
		one = ans[3][0]
	else:
		one = max(ans[2][0], ans[3][0])
	print(max(zero, one))


def diff(od, ev):
	(a, b) = (0, 0)
	e = len(ev)
	o = len(od)
	i = 0
	j = 0
	ca = 0
	cb = 1
	while True:
		if i % 2 == 0:
			if i < o and ca == 0:
				a += od[i]
				ca = 1
			if i < e and cb == 1:
				b += ev[i]
				cb = 0
		else:
			if i < o and cb == 0:
				b += od[i]
				cb = 1
			if i < e and ca == 1:
				a += ev[i]
				ca = 0
		if i >= o and i >= e:
			break
		i += 1
	return (a, b)

def same(od, ev):
	(a, b) = (0, 0)
	e = len(ev)
	o = len(od)
	if o == 0:
		return (0, 0)
	i = 0
	j = 0
	k = 0
	ca = 0
	cb = 0
	while True:
		if k % 2 == 0:
			if i < o and ca == 0:
				a += od[i]
				ca = 1
			if i + 1 < o and cb == 0:
				b += od[i + 1]
				cb = 1
			i += 2
		else:
			if j < e and ca == 1:
				a += ev[j]
				ca = 0
			if j + 1 < e and cb == 1:
				b += ev[j + 1]
				cb = 0
			j += 2
		if i >= o and j >= e:
			break
		k += 1
	if o == 1:
		b = 0
	return (a, b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ev = []
	od = []
	for ele in arr:
		if ele & 1:
			od.append(ele)
		else:
			ev.append(ele)
	od.sort(reverse=True)
	ev.sort(reverse=True)
	(a1, b1) = diff(od, ev)
	(a2, b2) = same(od, ev)
	(a3, b3) = diff(ev, od)
	(a4, b4) = same(ev, od)
	a = 0
	b = 0
	if b1 > b2:
		a = a1
	else:
		a = a2
	if b3 > b4:
		b = a3
	else:
		b = a4
	ans = max(a, b)
	print(ans)


def diff(od, ev):
	(a, b) = (0, 0)
	e = len(ev)
	o = len(od)
	i = 0
	j = 0
	ca = 0
	cb = 1
	while True:
		if i % 2 == 0:
			if i < o and ca == 0:
				a += od[i]
				ca = 1
			if i < e and cb == 1:
				b += ev[i]
				cb = 0
		else:
			if i < o and cb == 0:
				b += od[i]
				cb = 1
			if i < e and ca == 1:
				a += ev[i]
				ca = 0
		if i >= o and i >= e:
			break
		i += 1
	return (a, b)

def same(od, ev):
	(a, b) = (0, 0)
	e = len(ev)
	o = len(od)
	if o == 0:
		return (0, 0)
	i = 0
	j = 0
	k = 0
	ca = 0
	cb = 0
	while True:
		if k % 2 == 0:
			if i < o and ca == 0:
				a += od[i]
				ca = 1
			if i + 1 < o and cb == 0:
				b += od[i + 1]
				cb = 1
			i += 2
		else:
			if j < e and ca == 1:
				a += ev[j]
				ca = 0
			if j + 1 < e and cb == 1:
				b += ev[j + 1]
				cb = 0
			j += 2
		if i >= o and j >= e:
			break
		k += 1
	if o == 1:
		b = 0
	return (a, b)

def f(a):
	return a[0] - a[1]

def cal(a1, b1, a2, b2):
	(a, b) = (0, 0)
	if b1 == b2:
		a = max(a1, a2)
		b = b1
	elif a1 == a2:
		a = a1
		b = max(b1, b2)
	else:
		check = True
		if a1 >= b1:
			if b1 >= b2:
				(a, b) = (a1, b1)
				check = False
		if a2 >= b2 and check:
			if b2 >= b1:
				(a, b) = (a2, b2)
				check = False
		if check:
			if a1 >= b1:
				(a, b) = (a1, b1)
			else:
				(a, b) = (a2, b2)
	return (a, b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ev = []
	od = []
	for ele in arr:
		if ele & 1:
			od.append(ele)
		else:
			ev.append(ele)
	od.sort(reverse=True)
	ev.sort(reverse=True)
	(a1, b1) = same(od, ev)
	(a2, b2) = diff(od, ev)
	if b2 > b1:
		a = a2
		b = b2
	else:
		a = a1
		b = b2
	(a1, b1) = same(ev, od)
	(a2, b2) = diff(ev, od)
	tm = a
	if b2 > b1:
		a = a2
		b = b2
	else:
		a = a1
		b = b2
	print(max(a, tm))


def caltwoalt(even, odd):
	i = 0
	leno = len(odd)
	lene = len(even)
	c = 0
	f1 = False
	f2 = False
	while True:
		if i % 2 == 0:
			if i >= lene:
				break
			c += even[i]
		else:
			if i >= leno:
				break
			c += odd[i]
		i += 1
	return c

def calalt(even, odd, i):
	leno = len(odd)
	lene = len(even)
	c = 0
	while True:
		if i >= lene:
			break
		c += even[i]
		if i >= leno:
			break
		c += odd[i]
		i += 2
	return c
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = list()
	even = list()
	for x in l:
		if x & 1 == 1:
			odd.append(x)
		else:
			even.append(x)
	odd.sort(reverse=True)
	even.sort(reverse=True)
	saeven1 = calalt(even, odd, 0)
	saeven2 = caltwoalt(even, odd)
	saodd1 = caltwoalt(odd, even)
	saodd2 = calalt(odd, even, 0)
	sbeven1 = calalt(even, odd, 1)
	sbeven2 = caltwoalt(odd, even)
	sbodd1 = caltwoalt(even, odd)
	sbodd2 = calalt(odd, even, 1)
	temp = list()
	if sbeven1 > sbeven2:
		temp.append(saeven1)
	elif sbeven1 < sbeven2:
		temp.append(saeven2)
	else:
		temp.append(max(saeven1, saeven2))
	if sbodd1 > sbodd2:
		temp.append(saodd1)
	elif sbodd1 < sbodd2:
		temp.append(saodd2)
	else:
		temp.append(max(saodd1, saodd2))
	print(max(temp))


from sys import stdin, stdout
from collections import defaultdict, Counter
import math, heapq
input = stdin.readline

def func(flag1, flag2, arr):

	def sub(temp, flag):
		if flag:
			ele = 0
			if even:
				ele = -1 * heapq.heappop(even)
		else:
			ele = 0
			if odd:
				ele = -1 * heapq.heappop(odd)
		temp += ele
		if ele == 0:
			return (temp, -1)
		else:
			return (temp, 1 - flag)
	odd = [-1 * num for num in arr if num % 2 == 1]
	even = [-1 * num for num in arr if num % 2 == 0]
	heapq.heapify(odd)
	heapq.heapify(even)
	turn = 1
	(temp1, temp2) = (0, 0)
	while True:
		if turn % 2 == 1:
			if flag1 != -1:
				(temp1, flag1) = sub(temp1, flag1)
		elif flag2 != -1:
			(temp2, flag2) = sub(temp2, flag2)
		if flag1 == -1 and flag2 == -1:
			break
		turn += 1
	return (temp1, temp2)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	ans = 0
	pair1 = func(0, 0, arr)
	pair2 = func(0, 1, arr)
	if pair1[1] == pair2[1]:
		ans = max(ans, max(pair1[0], pair2[0]))
	elif pair1[1] > pair2[1]:
		ans = max(ans, pair1[0])
	else:
		ans = max(ans, pair2[0])
	pair1 = func(1, 0, arr)
	pair2 = func(1, 1, arr)
	if pair1[1] == pair2[1]:
		ans = max(ans, max(pair1[0], pair2[0]))
	elif pair1[1] > pair2[1]:
		ans = max(ans, pair1[0])
	else:
		ans = max(ans, pair2[0])
	print(ans)


from heapq import *

def scorer_helper(eh, oh, p1_eve, p2_eve):
	s1 = 0
	s2 = 0
	while True:
		flag = False
		if p1_eve and eh:
			flag = True
			s1 -= heappop(eh)
			p1_eve = not p1_eve
		elif not p1_eve and oh:
			flag = True
			s1 -= heappop(oh)
			p1_eve = not p1_eve
		if p2_eve and eh:
			flag = True
			s2 -= heappop(eh)
			p2_eve = not p2_eve
		elif not p2_eve and oh:
			flag = True
			s2 -= heappop(oh)
			p2_eve = not p2_eve
		if flag == False:
			break
	return (s1, s2)

def scorer(eh, oh, p1_even):
	(s11, s12) = scorer_helper(eh[:], oh[:], p1_even, True)
	(s21, s22) = scorer_helper(eh[:], oh[:], p1_even, False)
	if s12 == s22:
		return max(s11, s12)
	elif s12 > s22:
		return s11
	return s21
t = int(input())
for _ in range(t):
	a = int(input())
	points = list(map(int, input().split()))
	oddheap = []
	evenheap = []
	for e in points:
		if e % 2 == 1:
			heappush(oddheap, -e)
		else:
			heappush(evenheap, -e)
	pe = scorer(evenheap[:], oddheap[:], True)
	po = scorer(evenheap[:], oddheap[:], False)
	res = max(pe, po)
	print(res)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

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

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		arr = lis()
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		even.sort()
		odd.sort()
		p = [[0, 0], [1, 1], [0, 1], [1, 0]]
		res = [inf] * 2
		(prevalice, prevbob) = ([-inf] * 2, [-inf] * 2)
		ans = inf
		for (i, j) in p:
			(alice, bob) = (0, 0)
			(a, b) = (True, True)
			(aliceflag, bobflag) = (i, j)
			(p, q) = (even.copy(), odd.copy())
			while a or b:
				if a:
					if aliceflag % 2 == 0:
						if len(even) > 0:
							alice += even.pop()
						else:
							a = False
					elif len(odd) > 0:
						alice += odd.pop()
					else:
						a = False
					aliceflag ^= 1
				if b:
					if bobflag % 2 == 0:
						if len(even) > 0:
							bob += even.pop()
						else:
							b = False
					elif len(odd) > 0:
						bob += odd.pop()
					else:
						b = False
					bobflag ^= 1
			(even, odd) = (p.copy(), q.copy())
			if prevbob[i] < bob or prevalice[i] < alice:
				res[i] = min(res[i], max(alice, bob))
				prevalice[i] = max(prevalice[i], alice)
				prevbob[i] = max(prevbob[i], bob)
		print(max(res))
main()