Chef has with him an array A of length N. In one move, he can delete any element from A.

Find the minimum number of deletions Chef must make so that the following condition holds:
Let B denote the resulting array, and M be the length of B.
Then, B_{i} \oplus B_{j} ≤ 1 for every 1 ≤ i, j ≤ M.

Here, \oplus denotes the [bitwise XOR] operation.

For example, [3, 3, 3] and [6, 7, 6, 7] are valid final arrays, while [1, 2] and [6, 7, 8] are not (because 1 \oplus 2 = 3 and 7\oplus 8 = 15, respectively).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, denoting the length of array A.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — the elements of array A.

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

For each test case, output on a new line the answer: the minimum number of deletions required so that the given condition is satisfied.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 3\cdot 10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
2 2 2 2
5
3 4 3 4 4
5
1 2 3 4 0
6
5 5 5 6 6 6

----- Sample Output 1 ------ 
0
2
3
3

----- explanation 1 ------ 
Test case $1$: The given array already satisfies the condition, no deletions need to be done.

Test case $2$: Chef can delete both the $3$'s to make the array $[4, 4, 4]$, which satisfies the condition.

Test case $3$: Chef can use three moves as follows:
- Delete the $1$, the array is now $[2, 3, 4, 0]$.
- Delete the $4$, the array is now $[2, 3, 0]$.
- Delete the $0$, the array is now $[2, 3]$ which satisfies the condition.

It can be verified that using two or less deletions cannot give an array that satisfies the condition.

Test case $4$: Chef must either delete all the $5$'s or all the $6$'s.

Source: codechef | Difficulty: MEDIUM
Tags: Data structures


Solutions:
import math
t = int(input())
for kkk in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in range(n):
		d[a[i]] = d.get(a[i], 0) + 1
	max_ans = 0
	for i in d:
		ans = d[i]
		if i - 1 in d and i ^ i - 1 <= 1:
			ans += d[i - 1]
		max_ans = max(ans, max_ans)
	print(n - max_ans)


for _ in range(int(input())):
	l = [0]
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n + 5):
		l.append(0)
	for i in range(n):
		l[a[i]] += 1
	m = 0
	for i in range(0, n + 2, 2):
		if l[i] + l[i + 1] > m:
			m = l[i] + l[i + 1]
	print(n - m)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	p = l[0]
	k = [[p, 1]]
	for i in range(1, n):
		if k[-1][0] == l[i]:
			k[-1][1] += 1
		else:
			k += [[l[i], 1]]
	k.sort()
	m = 0
	p = 0
	l = len(k)
	for i in range(len(k)):
		if p:
			p = 0
			continue
		if k[i][0] % 2:
			if k[i][1] > m:
				m = k[i][1]
		elif i != l - 1:
			if k[i][0] - k[i + 1][0] == -1:
				if k[i][1] + k[i + 1][1] > m:
					m = k[i][1] + k[i + 1][1]
				p = 1
			elif k[i][1] > m:
				m = k[i][1]
		elif k[i][1] > m:
			m = k[i][1]
	print(n - m)


import math

def main(arr, l):
	arr.sort()
	dct = dict()
	M_value = 0
	for _ in arr:
		if _ not in dct:
			dct[_] = 1
		else:
			dct[_] += 1
		if dct[_] > M_value:
			M_value = dct[_]
	for _ in dct.keys():
		if _ % 2 == 0:
			next = _ + 1
			if next in dct.keys():
				r = dct[next] + dct[_]
				if r > M_value:
					M_value = r
	return l - M_value
for _ in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))[:l]
	print(main(arr, l))


for _ in range(int(input())):
	n = int(input())
	flag = 0
	mask = ~(1 << 0)
	size = input()
	a = size.split(' ')
	for j in range(n):
		a[j] = int(a[j]) & mask
	idx = []
	for k in range(n + 2):
		idx.append(0)
	for l in range(n):
		idx[a[l]] = idx[a[l]] + 1
		flag = max(flag, idx[a[l]])
	print(n - flag)


for i in range(0, int(input())):
	zz = int(input())
	arr = list(map(int, input().split()))
	dicti = {}
	maxi = 1
	for i in range(0, len(arr)):
		if arr[i] in dicti.keys():
			dicti[arr[i]] = dicti[arr[i]] + 1
			if dicti[arr[i]] > maxi:
				maxi = dicti[arr[i]]
		else:
			dicti[arr[i]] = 1
	for j in dicti.keys():
		if j % 2 == 0:
			p = j + 1
			if p in dicti.keys():
				u = dicti[p] + dicti[j]
				if u > maxi:
					maxi = u
	print(zz - maxi)


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = collections.Counter(a)
	longest = 0
	length = 0
	for key in d:
		if key % 2 == 0:
			if key + 1 in d:
				length = d[key] + d[key + 1]
			else:
				length = d[key]
		else:
			length = d[key]
		if longest < length:
			longest = length
	min_opt = n - longest
	print(min_opt)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ma = 0
	count = 1
	for i in range(1, n):
		if a[i] ^ a[i - 1] <= 1:
			count += 1
		else:
			ma = max(ma, count)
			count = 1
	ma = max(ma, count)
	print(n - ma)


import collections
T = int(input())
for x in range(T):
	n = int(input())
	a = collections.Counter([*map(int, input().split())])
	m = max((a[k] + [a[k + 1], a[k - 1]][k % 2] for k in a))
	print(n - m)


import sys
import collections
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	a = collections.Counter([*map(int, input().split())])
	m = max((a[k] + [a[k + 1], a[k - 1]][k % 2] for k in a))
	print(n - m)


import collections
for i in range(int(input())):
	n = int(input())
	a = collections.Counter([*map(int, input().split())])
	print(n - max((a[k] + [a[k + 1], a[k - 1]][k % 2] for k in a)))


for t in range(int(input())):
	size = int(input())
	li = list(map(int, input().split()))
	d = {}
	for i in li:
		try:
			d[i] += 1
		except:
			d[i] = 1
	c = []
	for i in d:
		c.append(d[i])
		try:
			if i ^ i + 1 == 1:
				c.append(d[i] + d[i + 1])
		except:
			a = 2
	print(size - max(c))


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [x | 1 for x in a]
	c = Counter(b)
	print(n - max(c.values()))


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	k = list(c.keys())
	v = list(c.values())
	k.sort()
	maxval = 0
	for i in range(len(k) - 1):
		if k[i] + 1 == k[i + 1] and k[i] % 2 == 0:
			if c[k[i]] + c[k[i + 1]] > maxval:
				maxval = c[k[i]] + c[k[i + 1]]
		if c[k[i]] > maxval:
			maxval = c[k[i]]
	if c[k[-1]] > maxval:
		maxval = c[k[-1]]
	print(n - maxval)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	freq = [0] * (n + 1)
	for i in l:
		freq[i] += 1
	m = freq[0]
	for i in range(len(freq)):
		if i % 2 != 0:
			m = max(m, freq[i] + freq[i - 1])
	if n % 2 == 0:
		m = max(m, freq[n])
	print(n - m)


from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = defaultdict(int)
	c = Counter(l)
	ans = 0
	for x in c.keys():
		if x ^ x + 1 == 1:
			ans = max(ans, c[x] + c[x + 1])
		else:
			ans = max(ans, c[x])
	print(n - ans)


import sys
input = sys.stdin.readline

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

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

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

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

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = invr()
	dic = {}
	for a in A:
		x = a | 1
		if x in dic:
			dic[x] += 1
		else:
			dic[x] = 1
	ans.append(N - max(dic.values()))
outplt(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for j in a:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	mx1 = max(list(d.values()))
	mx2 = 0
	for k in d:
		if k % 2 == 0 and k + 1 in d:
			if d[k] + d[k + 1] > mx2:
				mx2 = d[k + 1] + d[k]
	print(n - max(mx1, mx2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(c, m) = (0, 0)
	for i in range(n - 1):
		if a[i] == a[i + 1] or (a[i] % 2 == 0 and a[i + 1] == a[i] + 1):
			c += 1
		else:
			c = 0
		m = max(m, c)
	print(n - m - 1)


def app(l):
	a = []
	m = {}
	for i in l:
		if i % 2:
			a.append(i - 1)
		else:
			a.append(i)
	for i in a:
		if i in m:
			m[i] = m[i] + 1
		else:
			m[i] = 1
	k = 0
	for i in m:
		if m[i] > k:
			k = m[i]
	return n - k
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	print(app(l))
	t -= 1


def ans(arr):
	arr.sort()
	i = 0
	j = 0
	cand = []
	done = False
	cmp = arr[i]
	while j < len(arr):
		if arr[j] == cmp:
			j += 1
			if j == len(arr):
				cand.append(j - i)
		elif arr[j] ^ cmp == 1:
			cmp = arr[j]
			if done is False:
				done = True
				j += 1
				if j == len(arr):
					cand.append(j - i)
			else:
				done = False
				cand.append(j - i)
				i = j
		else:
			cand.append(j - i)
			done = False
			cmp = arr[j]
			i = j
	return len(arr) - max(cand)
test_cases = int(input())
while test_cases != 0:
	d = input()
	d2 = list(map(int, input().split()))
	print(ans(d2))
	test_cases -= 1


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	count = dict()
	for i in range(n):
		if l[i] in count:
			count[l[i]] += 1
		else:
			count[l[i]] = 1
	if len(count) == 1:
		print('0')
		t -= 1
		continue
	ans = n
	maxi = 0
	for x in count:
		if count[x] > maxi:
			maxi = count[x]
		if x % 2 == 0 and x + 1 in count:
			delete = n - count[x] - count[x + 1]
			if delete < ans:
				ans = delete
	if ans == n or n - maxi < ans:
		print(n - maxi)
	else:
		print(ans)
	t -= 1


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	count = dict()
	for i in range(n):
		if l[i] % 2 != 0:
			l[i] -= 1
		if l[i] in count:
			count[l[i]] += 1
		else:
			count[l[i]] = 1
	maxi = 0
	for x in count:
		if count[x] > maxi:
			maxi = count[x]
	else:
		print(n - maxi)
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in input().split():
		i = int(i)
		if i in d.keys():
			d[i] = d[i] + 1
		else:
			d[i] = 1
	ans = n
	for i in d.keys():
		if i % 2 and i - 1 in d.keys():
			ans = min(n - (d[i] + d[i - 1]), ans)
	for i in d.keys():
		ans = min(n - d[i], ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = {}
	for i in arr:
		ans[i] = ans.get(i, 0) + 1
	if len(ans) == 1:
		print(0)
	elif len(ans) == 2:
		(a, b) = ans.keys()
		if a ^ b == 1:
			print(0)
		else:
			print(min(ans[a], ans[b]))
	else:
		res = max(ans.values())
		for i in ans.keys():
			j = i ^ 1
			if j in ans:
				res = max(ans[i] + ans[j], res)
		print(n - res)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for i in d:
		if i % 2 == 0:
			if i + 1 in d:
				c = max(c, d[i] + d[i + 1])
			else:
				c = max(c, d[i])
		else:
			c = max(c, d[i])
	print(n - c)


from collections import defaultdict
t = int(input())
while t > 0:
	n = int(input())
	x = [int(i) for i in input().split()]
	d = defaultdict(int)
	m = 0
	for i in x:
		d[i] += 1
	for i in d:
		if i % 2 == 0:
			if i + 1 in d:
				m = max(m, d[i] + d[i + 1])
			else:
				m = max(m, d[i])
		else:
			m = max(m, d[i])
	print(n - m)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	cache = {}
	for i in data:
		if i % 2 == 0:
			if (i, i + 1) in cache:
				cache[i, i + 1] += 1
			else:
				cache[i, i + 1] = 1
		elif (i - 1, i) in cache:
			cache[i - 1, i] += 1
		else:
			cache[i - 1, i] = 1
	maxer = -1
	for key in cache:
		maxer = max(maxer, cache[key])
	print(n - maxer)


from collections import Counter
T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	C = Counter(L)
	S = set(L)
	M = [0]
	for i in S:
		count = 0
		if i ^ i + 1 <= 1:
			count += C[i]
			if i + 1 in S:
				count += C[i + 1]
			M.append(count)
	print(min(N - max(C.values()), N - max(M)))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hashmap = {}
	for e in arr:
		if e in hashmap:
			hashmap[e] += 1
		else:
			hashmap[e] = 1
	take = float('-inf')
	for k in hashmap:
		cur = hashmap[k]
		if k % 2 == 0 and k + 1 in hashmap:
			cur += hashmap[k + 1]
		take = max(take, cur)
	print(n - take)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	b = 0
	s = set(a)
	for i in s:
		x = d[i]
		if i ^ 1 in s:
			x += d[i ^ 1]
		b = max(b, x)
	print(n - b)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	count = []
	for i in d:
		ans = n - d[i]
		if i % 2 == 0:
			if i + 1 in d:
				ans -= d[i + 1]
		elif i - 1 in d:
			ans -= d[i - 1]
		count.append(ans)
	print(min(count))


from collections import Counter
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	counter = Counter(a)
	x = [counter[i] + counter[i ^ 1] for i in a]
	print(n - max(x))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	dick = {}
	for i in s:
		dick[i] = dick.get(i, 0) + 1
	if len(dick) == 1:
		print(0)
	elif len(dick) == 2:
		(a, b) = dick.keys()
		if a ^ b == 1:
			print(0)
		else:
			print(min(dick[a], dick[b]))
	else:
		maxi = max(dick.values())
		for i in dick.keys():
			x = i ^ 1
			if x in dick:
				maxi = max(dick[i] + dick[x], maxi)
		answer = n - maxi
		print(answer)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	count = 1
	b = []
	for j in range(n):
		if a[j] % 2 == 0:
			if a[j] == a[j - 1]:
				count += 1
			else:
				b.append(count)
				count = 1
		elif a[j] == a[j - 1]:
			count += 1
		elif a[j] == a[j - 1] + 1:
			count += 1
		else:
			b.append(count)
			count = 1
	b.append(count)
	print(max(0, n - max(b)))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if A.count(A[0]) == N:
		print(0)
	else:
		freq = {}
		for item in A:
			if item not in freq.keys():
				freq[item] = 0
			freq[item] += 1
		List = []
		for item in freq:
			val = N - freq[item]
			if item % 2 == 0:
				if item + 1 in freq.keys():
					val -= freq[item + 1]
			elif item - 1 in freq.keys():
				val -= freq[item - 1]
			List.append(val)
		print(min(List))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	temp = 0
	for i in s:
		a = d[i]
		if i ^ 1 in s:
			a += d[i ^ 1]
		temp = max(temp, a)
	print(n - temp)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	num = 0
	for i in d:
		p = d[i]
		if i & 1 == 0 and d.get(i + 1):
			p += d[i + 1]
		num = max(num, p)
	print(n - num)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	d = {}
	for j in l:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	c = 0
	for j in s:
		m = d[j]
		if j ^ 1 in s:
			m += d[j ^ 1]
		c = max(c, m)
	print(n - c)


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	arr = list(map(lambda x: x >> 1, arr))
	frequencyDict = {}
	for num in arr:
		if num in frequencyDict.keys():
			frequencyDict[num] += 1
		else:
			frequencyDict[num] = 1
	frequencies = frequencyDict.values()
	max_freq = max(frequencies)
	print(N - max_freq)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	d1 = {}
	ans = n
	for i in a:
		if i not in d1:
			d1[i] = 1
		else:
			d1[i] += 1
	for i in a:
		if i % 2 == 0:
			if d1.get(i + 1) != None:
				ans = min(ans, n - d1[i] - d1[i + 1])
			else:
				ans = min(ans, n - d1[i])
		else:
			ans = min(ans, n - d1[i])
	print(ans)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i not in d.keys():
			d[i] = 0
		d[i] += 1
	l = []
	for j in d.keys():
		vol = n - d[j]
		if j % 2 == 0:
			if j + 1 in d.keys():
				vol -= d[j + 1]
		elif j - 1 in d.keys():
			vol -= d[j - 1]
		l.append(vol)
	print(min(l))


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	unique_dict = {}
	for j in arr:
		if j in unique_dict:
			unique_dict[j] += 1
		else:
			unique_dict[j] = 1
	ans = 0
	for j in unique_dict.keys():
		temp = unique_dict[j]
		if j ^ j + 1 == 1 and j + 1 in unique_dict:
			temp += unique_dict[j + 1]
		ans = max(ans, temp)
	print(length - ans)


from collections import Counter, defaultdict
import sys

def sol(n, A):
	d = defaultdict(int)
	for i in range(n):
		num = A[i]
		count = 0
		s = ''
		while num > 0:
			if num % 2 == 1:
				s = str(1) + s
			else:
				s = str(0) + s
			num //= 2
		d[s[:-1] + '*'] += 1
	ans = 0
	for i in d:
		ans = max(ans, d[i])
	return n - ans
input = sys.stdin.readline

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

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

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	arr = inlt()
	print(sol(n, arr))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	j = sorted(list(set(x)))
	d = dict()
	mx = 0
	for i in x:
		if i in d:
			d[i] += 1
			mx = max(mx, d[i])
		else:
			d[i] = 1
			mx = max(mx, d[i])
	for k in range(len(j) - 1):
		if j[k] % 2 == 0 and j[k] + 1 == j[k + 1]:
			mx = max(mx, d[j[k]] + d[j[k + 1]])
	print(n - mx)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	counta = {}
	for x in a:
		xstr = '{:b}'.format(x)[:-1]
		if xstr in counta:
			counta[xstr] = counta[xstr] + 1
		else:
			counta[xstr] = 1
	tot = len(a)
	maxocc = max(counta.values())
	if len(counta) > 1:
		print(tot - maxocc)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	x = l[0] ^ 1
	if x in d:
		y = d[x]
	else:
		y = 0
	m = n - d[l[0]] - y
	for i in range(1, len(l)):
		x = l[i] ^ 1
		if x in d:
			y = d[x]
		else:
			y = 0
		m = min(m, n - d[l[i]] - y)
	print(m)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	freq = {}
	for item in A:
		if item not in freq.keys():
			freq[item] = 0
		freq[item] += 1
	new_list = []
	for ki in freq:
		val = N - freq[ki]
		if ki % 2 == 0:
			if ki + 1 in freq.keys():
				val -= freq[ki + 1]
		elif ki - 1 in freq.keys():
			val -= freq[ki - 1]
		new_list.append(val)
	print(min(new_list))


t = int(input())
for i in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	j = 0
	d = {}
	for j in l:
		if j not in d.keys():
			d[j] = 0
		d[j] += 1
	j = 0
	p = 0
	k = []
	for j in d.keys():
		p = len(l) - d[j]
		if j % 2 == 0:
			if j + 1 in d.keys():
				p -= d[j + 1]
		elif j - 1 in d.keys():
			p -= d[j - 1]
		k.append(p)
	print(min(k))


for i in range(int(input())):
	n = int(input())
	freq = {}
	my_list = list(map(int, input().split()))
	for item in my_list:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	l = []
	for k in freq.keys():
		val = n - freq[k]
		if k % 2 == 0:
			if k + 1 in freq.keys():
				val -= freq[k + 1]
		elif k - 1 in freq.keys():
			val -= freq[k - 1]
		l.append(val)
	print(min(l))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l3 = []
	val = 0
	d = Counter(l)
	for i in d.keys():
		if i % 2 == 0:
			if i + 1 in d.keys():
				val = n - d[i]
				val = val - d[i + 1]
			else:
				val = n - d[i]
		elif i - 1 in d.keys():
			val = n - d[i]
			val = val - d[i - 1]
		else:
			val = n - d[i]
		l3.append(val)
	print(min(l3))


time = int(input())
for _ in range(time):
	le = int(input())
	array = list(map(int, input().split()))
	d = {}
	for i in array:
		if i not in d.keys():
			d[i] = 0
		d[i] += 1
	count = []
	for i in d.keys():
		var = le - d[i]
		if i % 2 == 0:
			if i + 1 in d.keys():
				var -= d[i + 1]
		elif i - 1 in d.keys():
			var -= d[i - 1]
		count.append(var)
	print(min(count))


import collections
for _ in range(int(input())):
	print(int(input()) - collections.Counter([a // 2 for a in list(map(int, input().split()))]).most_common(1)[0][1])


import collections
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	counter = collections.Counter([a // 2 for a in A])
	print(len(A) - counter.most_common(1)[0][1])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	m = 0
	for i in d:
		if i & i + 1 != 0 and i + 1 in d and (i % 2 == 0):
			m = max(m, d[i] + d[i + 1])
		else:
			m = max(m, d[i])
	print(n - m)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(len(a)):
		if a[i] & 1:
			a[i] = a[i] - 1
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	print(n - max(d.values()))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [a // 2 for a in arr]
	count = Counter(arr)
	print(n - max(count.values()))


from collections import Counter
t = int(input())
while t:
	n = int(input())
	l = [int(x) for x in input().split()]
	d = Counter(l)
	l = [x for x in d.values()]
	l2 = [x for x in d.keys()]
	l2.sort()
	r1 = 0
	r = max(l)
	for i in l2:
		c = 0
		if i ^ i + 1 <= 1:
			if i in d.keys():
				c += d[i]
			if i + 1 in d.keys():
				c += d[i + 1]
			r1 = max(r1, c)
	print(min(n - r, n - r1))
	t -= 1


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ct = Counter(a)
	ans = n
	for k in ct:
		temp = ct[k]
		nxt = k + (-1) ** (k & 1)
		if nxt in ct:
			temp += ct[nxt]
		ans = min(ans, n - temp)
	print(ans)


for trie in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	c = 0
	s = list(set(lst))
	d = {}
	for i in range(n):
		lst[i] = lst[i] // 2
	for i in lst:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	max1 = 0
	for i in d.keys():
		if d[i] > max1:
			max1 = d[i]
	print(n - max1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 1
	cnt = 1
	for i in range(len(arr) - 1):
		if arr[i] ^ arr[i + 1] <= 1:
			cnt += 1
			ans = max(cnt, ans)
		else:
			cnt = 1
	print(n - ans)


from collections import Counter
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	l = list(map(int, input().split()))
	n_c = Counter(l)
	c = [0]
	for i in n_c.keys():
		if i % 2 == 0:
			if i + 1 in n_c.keys():
				c.append(n_c[i] + n_c[i + 1])
	k = max(c)
	p = max(n_c.values())
	print(min(n - k, n - p))