An even sequence has the following property: each maximal contiguous subsequence which contains only equal integers (i.e. the same integer repeated a number of times) has an even length. In particular, the empty sequence is even. A subsequence is maximal if it is not contained in a larger contiguous subsequence which contains only equal integers.
Chef was given an integer sequence $A_1, A_2, \ldots, A_N$ by his friend Mr. Z. He may perform the following operation any number of times: either delete an element of the current sequence (if it is non-empty) or insert an integer anywhere in the current sequence (possibly at the beginning or at the end).
Find the minimum number of operations needed to make the sequence even.

-----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, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum number of operations.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 2 \cdot 10^5$
- $1 \leq A_i \leq N$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Subtasks-----
Subtask #1 (10 points): $N \leq 18$
Subtask #2 (10 points): $A_i \leq A_{i+1}$ for each valid $i$
Subtask #3 (20 points): $N \leq 3,000$
Subtask #4 (20 points): $A_i \leq 26$ for each valid $i$
Subtask #5 (40 points): original constraints

-----Example Input-----
2
4
1 1 2 1
11
2 2 2 10 2 10 1 1 5 3 5

-----Example Output-----
2
3

-----Explanation-----
Example case 1: Here are two ways to make the sequence even using $2$ operations:
- Delete the first element $1$ and the only element $2$, resulting in a sequence $(1, 1)$, which is even.
- Delete the last element $1$ and insert $2$ at the end, resulting in a sequence $(1,1,2,2)$, which is even.
It can be proved that one operation is not enough to make the initial sequence even.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	dp = [-1 for i in range(0, n + 1)]
	for i in a:
		var1 = dp[i]
		var2 = ans
		ans = max(ans, var1 + 1)
		dp[i] = max(dp[i], var2 + 1)
	print(n - ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [-1] * (n + 1)
	dp[0] = 0
	for k in l:
		even = dp[0]
		odd = dp[k]
		dp[k] = max(odd, even + 1)
		dp[0] = max(even, odd + 1)
	print(n - dp[0])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [-1] * (n + 1)
	dp[0] = 0
	for e in arr:
		even = dp[0]
		odd = dp[e]
		dp[e] = max(odd, even + 1)
		dp[0] = max(even, odd + 1)
	print(n - dp[0])


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set()
	count = 0
	for i in l:
		if i in s:
			count += 2
			s.clear()
		else:
			s.add(i)
	print(n - count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	li = []
	count = 0
	for i in l:
		if i in li:
			count += 2
			li = []
		else:
			li.append(i)
	print(n - count)


def solve(s):
	seen = set()
	out = 0
	for c in s:
		if c in seen:
			out += len(seen) - 1
			seen = set()
		else:
			seen.add(c)
	return out + len(seen)
for tc in range(int(input())):
	input()
	s = [int(x) for x in input().strip().split(' ')]
	print(solve(s))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	isContinuing = set()
	ans = 0
	for i in l:
		lengthOfSet = len(isContinuing)
		isContinuing.add(i)
		if lengthOfSet == len(isContinuing):
			ans += 2
			isContinuing.clear()
	print(n - ans)


import sys
from math import inf

def solve(A):
	dp = [-inf for _ in range(len(A) + 1)]
	dp[0] = 0
	for (i, a) in enumerate(A):
		even = dp[0]
		odd = dp[a]
		dp[a] = max(dp[a], even + 1)
		dp[0] = max(dp[0], odd + 1)
	return len(A) - dp[0]

def main():
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		N = int(sys.stdin.readline())
		A = [int(i) for i in sys.stdin.readline().split()]
		soln = solve(A)
		print(soln)

def __starting_point():
	main()
__starting_point()


import sys
from math import inf

def solve(A):
	prev = 0
	count = 0
	ops = 0
	for (i, a) in enumerate(A):
		if a == prev:
			count += 1
		elif count % 2:
			if i + 1 < len(A) and A[i + 1] == prev:
				ops += 1
			else:
				ops += 1
				count = 1
				prev = a
		else:
			count = 1
			prev = a
	if count % 2:
		ops += 1
	return ops

def main():
	sys.setrecursionlimit(pow(10, 9))
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		N = int(sys.stdin.readline())
		A = [int(i) for i in sys.stdin.readline().split()]
		soln = solve(A)
		print(soln)

def __starting_point():
	main()
__starting_point()


import sys
from math import inf

def solve(i, prev, cnt, ops, A, acc):
	if i >= len(A):
		if cnt % 2 == 0:
			return ops
		else:
			return inf
	if cnt >= acc:
		return acc
	result = acc
	if A[i] == prev:
		result = min(result, solve(i + 1, prev, cnt + 1, ops, A, result))
	elif cnt % 2:
		result = min(result, solve(i + 1, A[i], 1, ops + 1, A, result))
		result = min(result, solve(i + 1, prev, cnt, ops + 1, A, result))
	else:
		result = min(result, solve(i + 1, prev, cnt, ops + 1, A, result))
		result = min(result, solve(i + 1, A[i], 1, ops, A, result))
	return result

def main():
	sys.setrecursionlimit(pow(10, 9))
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		N = int(sys.stdin.readline())
		A = [int(i) for i in sys.stdin.readline().split()]
		soln = solve(0, 0, 0, 0, A, inf)
		print(soln)

def __starting_point():
	main()
__starting_point()


import sys
from functools import partial
SAMPLE_IN = 'sample.in'
SAMPLE_ANS = 'sample.ans'

def read_int(f) -> int:
	return int(f.readline())

def read_ints(f) -> list:
	return [int(x) for x in f.readline().split()]

def read_case(f=sys.stdin) -> tuple:
	n = read_int(f)
	nums = read_ints(f)
	return (n, nums)

def solve(n, nums):
	even = 0
	odd = [-1] * (n + 1)
	for x in nums:
		(even, odd[x]) = (max(even, odd[x] + 1), even + 1)
	return n - even

def make_submission(fin=sys.stdin, fout=sys.stdout):
	output = partial(print, file=fout)
	n_cases = int(fin.readline())
	for t in range(1, n_cases + 1):
		case = read_case(fin)
		answer = solve(*case)
		output(answer)

def __starting_point():
	import os
	if os.getenv('GCJ_LOCAL'):
		with open(SAMPLE_IN) as s:
			make_submission(s)
	else:
		make_submission()
__starting_point()


from collections import defaultdict as dd
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	stacks = dd(lambda : -10 ** 9)
	c = temp = 0
	for i in a:
		temp = c
		c = max(c, stacks[i] + 1)
		stacks[i] = max(stacks[i], temp + 1)
	print(n - c)


import sys
T = int(input())
for i in range(T):
	n = int(input())
	seq = list(map(int, input().split(' ')))
	t = [-sys.maxsize - 1 for i in range(n + 1)]
	t[0] = 0
	for x in seq:
		even = t[0]
		odd = t[x]
		t[x] = max(odd, even + 1)
		t[0] = max(even, odd + 1)
	print(n - t[0])


from sys import stdin, stdout
input = stdin.readline

def f(arr):
	ans = 0
	val = 0
	s = -1
	for i in arr:
		if i != s:
			ans += val % 2
			val = 1
			s = i
		else:
			val += 1
	ans += val % 2
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n > 18:
		print(f(arr))
		continue
	ans = float('inf')
	for mask in range(0, 1 << n):
		vals = []
		c = 0
		for i in range(n):
			if mask & 1 << i:
				vals.append(arr[i])
			else:
				c += 1
		ans = min(ans, c + f(vals))
	stdout.write(str(ans) + '\n')


import sys
sys.setrecursionlimit(1000000)

def LCES(l, prevSel, parity, ind, length):
	if ind == len(l):
		if parity == 0:
			return length
		else:
			return -1
	elif parity == 0:
		left = LCES(l, l[ind], 1, ind + 1, length + 1)
		right = LCES(l, prevSel, 0, ind + 1, length)
		return max(left, right)
	elif prevSel != l[ind]:
		return LCES(l, prevSel, 1, ind + 1, length)
	else:
		left = LCES(l, l[ind], 0, ind + 1, length + 1)
		return left
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dp = {}
	left = LCES(l, l[0], 1, 1, 1)
	right = LCES(l, -1, 0, 1, 0)
	print(n - max(left, right))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	d = []
	for i in range(n + 1):
		d.append(-1)
	for i in a:
		(l, d[i]) = (max(l, d[i] + 1), max(d[i], l + 1))
	print(n - l)