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.

Difficulty: interview

Starter code:

Solutions:
'''Author- Akshit Monga'''
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)

# evens
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)

'''Author- Akshit Monga'''
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)

"""
Code Chef :: December 2020 Lunchtime :: Even Sequence Problem Code: EVSTR
https://www.codechef.com/LTIME91B/problems/EVSTR
"""
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():
 """Main program."""
 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()

"""
Code Chef :: December 2020 Lunchtime :: Even Sequence Problem Code: EVSTR
https://www.codechef.com/LTIME91B/problems/EVSTR
"""
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
  else:
   if count % 2:
    # I can fix this for on op or delete me for one op.
    if i + 1 < len(A) and A[i+1] == prev:
     # If delete me is the same as fixing it, delete me
     ops += 1
    else:
     # Fix it
     ops += 1
     count = 1
     prev = a
   else:
    count = 1
    prev = a
 if count % 2:
  ops += 1

 return ops


def main():
 """Main program."""
 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()

"""
Code Chef :: December 2020 Lunchtime :: Even Sequence Problem Code: EVSTR
https://www.codechef.com/LTIME91B/problems/EVSTR
"""
import sys
from math import inf


def solve(i, prev, cnt, ops, A, acc):
 # Base Case
 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))
 else:
  if cnt % 2:
   # If cnt is odd, we can
   # (1) Fix it and add current.  It will cost on op to fix.
   result = min(result, solve(i + 1, A[i], 1, ops + 1, A, result))
   # (2) Not fix it and delete current.
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A, result))
  else:
   # If cnt is even, we can
   # (1) Delete current
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A, result))
   # (2) Add current
   result = min(result, solve(i + 1, A[i], 1, ops, A, result))
 return result


def main():
 """Main program."""
 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()

"""
Code Chef :: December 2020 Lunchtime :: Even Sequence Problem Code: EVSTR
https://www.codechef.com/LTIME91B/problems/EVSTR
"""
import sys
from math import inf


def solve(i, prev, cnt, ops, A):
 # Base Case
 if i >= len(A):
  if cnt % 2 == 0:
   return ops
  else:
   return inf

 result = inf
 if A[i] == prev:
  result = min(result, solve(i + 1, prev, cnt + 1, ops, A))
 else:
  if cnt % 2:
   # If cnt is odd, we can
   # (1) Fix it and add current.  It will cost on op to fix.
   result = min(result, solve(i + 1, A[i], 1, ops + 1, A))
   # (2) Not fix it and delete current.
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A))
  else:
   # If cnt is even, we can
   # (1) Delete current
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A))
   # (2) Add current
   result = min(result, solve(i + 1, A[i], 1, ops, A))
 return result


def main():
 """Main program."""
 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)
  print(soln)


def __starting_point():
 main()

__starting_point()

"""
Code Chef :: December 2020 Lunchtime :: Even Sequence Problem Code: EVSTR
https://www.codechef.com/LTIME91B/problems/EVSTR
"""
import sys
from math import inf


def solve(i, prev, cnt, ops, A):
 # Base Case
 if i >= len(A):
  if cnt % 2 == 0:
   return ops
  else:
   return inf

 result = inf
 if A[i] == prev:
  result = min(result, solve(i + 1, prev, cnt + 1, ops, A))
 else:
  if cnt % 2:
   # If cnt is odd, we can
   # (1) Fix it and add current.  It will cost on op to fix.
   result = min(result, solve(i + 1, A[i], 1, ops + 1, A))
   # (2) Not fix it and delete current.
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A))
  else:
   # If cnt is even, we can
   # (1) Delete current
   result = min(result, solve(i + 1, prev, cnt, ops + 1, A))
   # (2) Add current
   result = min(result, solve(i + 1, A[i], 1, ops, A))
 return result


def main():
 """Main program."""
 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)
  print(soln)


def __starting_point():
 main()

__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)

# cook your dish here
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])
   
 


# cook your dish here
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)]
 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])
   
 


# cook your dish here
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)]
 t[0]=0
 for i in seq:
  x=i
  even=t[0]
  odd=t[x]
  
  t[x]=max(odd,even+1)
  t[0]=max(even,odd+1)
  
 print(n-t[0])
   
 


# cook your dish here
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)]
 t[0]=0
 even=t[0]
 odd=-sys.maxsize-1
 for i in seq:
  x=i
  even=t[0]
  odd=t[x]
  
  t[x]=max(odd,even+1)
  t[0]=max(even,odd+1)
  
 print(n-t[0])
   
 


'''Author- Akshit Monga'''
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
 else:
  if(parity==0):
   # if(dp.get(str(parity)+" "+str(ind))):
   #     return dp[str(parity)+" "+str(ind)]
   left = LCES(l, l[ind], 1, ind+1, length+1)
   right = LCES(l, prevSel, 0, ind+1, length)
   return max(left, right)
   # return dp[str(parity)+" "+str(ind)]
  else:
   if(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)