There is a task in Among Us in which $N$ temperature scale with unique readings are given and you have to make all of them equal. In one second you can choose an odd number and add or subtract that number in any one temperature value. Find minimum time (in seconds) required to complete the task.
$Note$: Equal value may or may not belong to array.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of each testcase contains single integer $N$, the number of temperature scales
- Next line contain $A_i$ for $1 \leq i \leq N$, reading of temperature scales

-----Output:-----
For each testcase, output a single line the time (in seconds) required to complete the task.

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^3$
- $0 \leq A_i \leq 10^9$

-----Sample Input:-----
3

5

1 2 3 4 5

4

5 2 3 8

2

50 53  

-----Sample Output:-----
5

4

1 

-----EXPLANATION:-----
- In the $2^{nd}$ test case we need $2$ seconds to change $2$ to $8$ , $1$ second to change $3$ and $5$ to $8$ . So total time required is $2+1+1=4$ seconds.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
for _ in range(int(input())):
 n=int(input())
 ar=list(map(int,input().split()))
 odd=0
 even=0
 if n==1:
  print(0)
  continue
 for i in range(n):
  if ar[i]%2==1:
   odd+=1
  else:
   even+=1
 if odd>0:
  vo=(odd-1)*2+even
 else:
  vo=even
 if even>0:
  ve=(even-1)*2+odd
 else:
  ve=odd
 print(min(vo,ve))


for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 ce=co=0
 if n==1:
  print(n-1)
 else:
  for i in a:
   if i%2==0:
    ce+=1
   else:
    co+=1
  if ce==0 or co==0:
   print(n)
  else:
   c1=max(co,ce)
   c2=min(co,ce)
   print(c1+2*(c2-1))

try:
 t=int(input())
 for _ in range(t):
  n=int(input())
  l=[int(x) for x in input().split()]
  if n==1:
   print(0)
   continue
  even,odd=0,0
  for i in range(n):
   if l[i]%2==0:
    even+=1
   else:
    odd+=1
  mx=max(even,odd)
  mn=min(even,odd)
  if mn>0:
   print(mx+(mn-1)*2)
  else:
   print(mx)
except EOFError:
 pass

for _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 ev=[]
 od=[]

 for i in a:
  if i%2==0:
   ev.append(i)
  else:
   od.append(i)
 c=0
 c1=0
 cc=0
 cc1=0
 if od:
  mo=max(od)
  for i in a:
   if i!=mo and i%2!=mo%2:
    c+=1
   elif i!=mo and i%2==mo%2:
    c+=2
  mo+=1
  for i in a:
   if i%2==mo%2:
    cc+=2
   else:
    cc+=1
  
 if ev:
  me=max(ev)
  for i in a:
   if i!=me and i%2==me%2:
    c1+=2
   elif i!=me and i%2!=me%2:
    c1+=1
  me+=1 #odd now
  for i in a:
   if i%2==me%2:  #odd odd 2
    cc1+=2
   else:
    cc1+=1 #odd even 1
 if ev and od:
  print(min(c,c1,cc,cc1))
 elif not ev:
  print(min(cc,c))
 elif not od:
  print(min(cc1,c1))

t = int(input())

for i in range(t):
 l = int(input())
 nums = list(map(int,input().split()))
 
 
 if l == 1:
  print(0)
  continue
 
 # print(nums)
 even,odd = 0,0
 
 for n in nums:
  if n%2 == 0:
   even += 1
   
  else:
   odd += 1
  
 less, more = 0,0
 
 if even >= odd:
  less = odd
  more = even
  
 else:
  less = even 
  more = odd
 
 if less > 0:
  print((less-1)*2 + more)
  
 else:
  print(more)


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 c=0
 for i in l:
  if i%2==0:
   c+=1
 if l[-1]%2==1:
  a1=c+(n-c-1)*2
  if c!=0:
   a2=(n-c)+2*(c-1)
  else:
   a2=n
  #print(a1,a2)
  if a1>a2:
   print(a2)
  else:
   print(a1)
 else:
  a1=(n-c)+(c-1)*2
  if c!=n:
   a2=c+(n-c-1)*2
  else:
   a2=n
  if a1>a2:
   print(a2)
  else:
   print(a1)

# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 even=0
 for a in l:
  if a%2==0:
   even+=1
 if l[-1]%2==0:
  a=(n-even)+(even-1)*2
  if even!=n:
   b=even+(n-even-1)*2
  else:
   b=n
  if a>b:
   print(b)
  else:
   print(a)
 else:
  a=even+(n-even-1)*2
  if even!=0:
   b=(n-even)+2*(even-1)
  else:
   b=n
  if a>b:
   print(b)
  else:
   print(a)

# cook your dish here
t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 odd=1000000001
 for i in a:
  if i%2!=0:
   odd=i
   break
 even=1000000002
 for i in a:
  if i%2==0:
   even=i
   break
 even_res=0
 odd_res=0
 for i in a:
  if i!=even:
   if abs(i-even)%2==0:
    even_res+=2
   else:
    even_res+=1
  if i!=odd:
   if abs(i-odd)%2==0:
    odd_res+=2
   else:
    odd_res+=1
 
   
   
   
 
  
 print(min(even_res,odd_res))


# cook your dish here
for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 l.sort()
 c=0
 for i in l:
  if i%2==0:
   c+=1
 if l[-1]%2==1:
  a1=c+(n-c-1)*2
  if c!=0:
   a2=(n-c)+2*(c-1)
  else:
   a2=n
  #print(a1,a2)
  if a1>a2:
   print(a2)
  else:
   print(a1)
 else:
  a1=(n-c)+(c-1)*2
  if c!=n:
   a2=c+(n-c-1)*2
  else:
   a2=n
  if a1>a2:
   print(a2)
  else:
   print(a1)

# cook your dish here
for _ in range(int(input())):
 N = int(input())
 array = list(map(int, input().split()))
 odds = 0
 even = 0
 for i in array:
  if i % 2 == 0:
   even += 1
  else:
   odds += 1

 if (even > 1):
  ans = odds + (even - 1) * 2
 else:
  ans = odds
 if odds > 1:
  ans = min(ans, even + (odds - 1) * 2)
 else:
  ans = min(ans, even)
 print(ans)

t = int(input())

while(t):
 t -= 1
 
 n = int(input())
 
 a = list(map(int,input().split()))
 
 odd,even = 0,0
 
 fo,fe = -1,-1
 for i in range(n):
  if (a[i]%2==1):
   fo = i
   break
 
 for i in range(n):
  if(a[i]%2==0):
   fe = i
   break
 
 for i in range(n):
  if i!=fo:
   if (a[i]%2==1):
    odd += 2
   else:
    odd += 1
 
 for i in range(n):
  if i!=fe:
   if (a[i]%2==1):
    even += 1
   else:
    even += 2
 
 print(min(odd,even))

for tc in range(int(input())):
 N = int(input())
 A = list(map(int, input().split()))

 trump = 1
 tmp1 = 0
 for i in A:
  if trump and i % 2 == 0:
   trump = 0
  elif i % 2 == 0:
   tmp1 += 2
  else:
   tmp1 += 1

 trump = 1
 tmp2 = 0
 for i in A:
  if trump and i % 2:
   trump = 0
  elif i % 2:
   tmp2 += 2
  else:
   tmp2 += 1

 print(min(tmp1, tmp2))

from sys import stdin,stdout
import math,bisect
from collections import Counter,deque,defaultdict
L=lambda:list(map(int, stdin.readline().strip().split()))
M=lambda:list(map(int, stdin.readline().strip().split()))
I=lambda:int(stdin.readline().strip())
S=lambda:stdin.readline().strip()
C=lambda:stdin.readline().strip().split()
def pr(a):return("".join(list(map(str,a))))
#_________________________________________________#
 
def solve():
 n = I()
 a = L()
 e=o=0
 for i in a:
  if i%2:
   o+=1
  else:
   e+=1
 d=defaultdict(int)
 for i in a:
  d[i]+=1
 ec=0
 oc=0
 for i in d:
  if i%2:
   oc=max(oc,d[i])
  else:
   ec=max(ec,d[i])
 print(min(o+2*(e-ec),2*(o-oc)+e))
for _ in range(I()):
 solve()


# cook your dish here
for t in range(int(input())):
 n=int(input())
 a=[int(i) for i in input().split()]
 even=0
 odd=0
 for i in a:
  if i%2==0:
   even+=1
  else:
   odd+=1
 if n==1:
  print(0)
 elif odd==0 or even==0:
  print(even+odd)
 else:
  x=(odd-1)*2+even
  y=(even-1)*2+odd
  print(min(x,y))

import sys
import math
from collections import defaultdict,Counter

input=sys.stdin.readline
def print(x):
 sys.stdout.write(str(x)+"\n")

# sys.stdout=open("CP1/output.txt",'w')
# sys.stdin=open("CP1/input.txt",'r')

# mod=pow(10,9)+7
t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 od=0
 for j in a:
  if j&1:
   od+=1
 ev=n-od
 ans=min(max(0,(od-1))*2+ev,max(0,(ev-1))*2+od)
 print(ans)