Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well. 

You are given N non-negative integers A_{1}, A_{2}, \ldots, A_{N}. You are allowed to perform following operation any number of times:

Choose any valid index i (1 ≤ i ≤ N) and a positive integer M>0 and replace A_{i} with A_{i}\bmod M. That is, replace A_{i} with its remainder when divided by M, which is a value between 0 and M-1, inclusive. 
M does not need to be same between different operations.

Find the minimum number of operations to make all the array elements equal.

Note: Since the input and output are large, prefer using fast input-output methods.

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

- The first line contains an integer T - the number of test cases. Then T test cases follow.
- The first line of each test case contains an integer N - the size of array.
- The second line contains N integers A_{1}, A_{2}, \ldots, A_{N} - the elements of the array.

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

For each test, print one line containing an integer which denotes minimum number of operations performed to make all the elements equal.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 2 \cdot 10^{9}$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
3
2 1 3
3
1 1 3

----- Sample Output 1 ------ 
3
1

----- explanation 1 ------ 
In first test case, we can make all the elements equal by following operations:
* Take $i = 1$ and $M = 2$ and do $A_{1} := A_{1} \bmod 2 = 0$.
* Take $i = 2$ and $M = 1$ and do $A_{2} := A_{2} \bmod 1 = 0$.
* Take $i = 3$ and $M = 3$ and do $A_{3} := A_{3} \bmod 3 = 0$.    
After these $3$ operations we have all the elements equal to zero.
    
In second test case, we can perform following operation: 
* Choose $i = 3$ and $M = 2$ and do $A_{3} := A_{3} \bmod 2 = 1$.    
After this operation all the elements are $1$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	m = min(a)
	flag = 0
	for i in a:
		if i - m <= m and m != i:
			flag = 1
			break
	if flag == 1:
		print(n)
	else:
		print(n - a.count(m))


from collections import Counter
a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	B = Counter(A)
	C = list(set(A))
	if len(C) == 1:
		print(0)
	else:
		C.sort()
		x = C[0]
		y = C[1]
		p = A.count(x)
		if y <= 2 * x:
			print(N)
		else:
			print(N - p)


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	m = L[0]
	a = 1
	ans = -1
	for i in range(1, n):
		if L[i] == m:
			a += 1
		else:
			ans = L[i]
			break
	if a == n:
		print(0)
	elif ans > 2 * m:
		print(n - a)
	else:
		print(n)


def snek(a, b):
	if a / 2 > b:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = n
	for j in set(l):
		c = 0
		s = j
		for k in range(n):
			if l[k] != j and (not snek(l[k], s)):
				break
			elif j != l[k]:
				c += 1
		else:
			ans = min(ans, c)
	print(ans)


def valid(a, b):
	if a / 2 > b:
		return True
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = n
	for i in set(l):
		c = 0
		el = i
		for j in range(n):
			if l[j] != i and (not valid(l[j], el)):
				break
			elif i != l[j]:
				c += 1
		else:
			ans = min(ans, c)
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = min(l)
	if n == 1:
		print(0)
	elif 0 in l:
		print(n - l.count(0))
	else:
		ans = n
		f = 1
		for i in l:
			if i > x and i <= 2 * x:
				f = 0
		if f:
			ans = min(ans, n - l.count(x))
		print(ans)


from math import gcd
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = 0
	for i in l:
		g = gcd(i, g)
	x = min(l)
	if n == 1:
		print(0)
	elif 0 in l:
		print(n - l.count(0))
	else:
		ans = n
		f = 1
		for i in l:
			if i > x and i <= 2 * x:
				f = 0
		if f:
			ans = min(ans, n - l.count(x))
		if 2 * g not in l:
			ans = min(ans, n - l.count(g))
		print(ans)


for t in range(int(input())):

	def solution():
		N = int(input())
		A = list(input().split())

		def get_key(val, dic):
			for (key, value) in dic.items():
				if val == value:
					return key
		for i in range(N):
			A[i] = int(A[i])
		dic = {}
		for element in A:
			if element not in dic:
				dic[element] = 0
			dic[element] += 1
		keys = sorted(dic.keys())
		import math
		if len(keys) == 1:
			return 0
		elif keys[1] <= 2 * keys[0]:
			return N
		else:
			return N - dic.get(keys[0])
	print(solution())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mini = min(a)
	cnt = a.count(mini)
	flag = False
	res = 0
	for i in a:
		if i != mini and i <= 2 * mini:
			flag = True
			break
	if flag:
		res = n
	else:
		res = n - cnt
	print(res)


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	min_v = min(A)
	min_c = A.count(min(A))
	flag = True
	for i in range(len(A)):
		if A[i] != min_v:
			if math.ceil(A[i] / 2) - 1 < min_v:
				flag = False
				break
	if flag:
		print(N - min_c)
	else:
		print(N)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mini = min(a)
	count = 0
	for i in range(n):
		if a[i] == mini:
			count = count + 1
	flag = False
	for i in range(n):
		if a[i] == mini:
			continue
		elif a[i] <= 2 * mini:
			flag = True
			break
		else:
			continue
	if flag == True:
		print(n)
	else:
		print(n - count)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	i = 0
	cnt = 0
	ans = 0
	while i < n and a[i] == a[0]:
		i += 1
	cnt = i
	while i < n:
		if a[i] <= 2 * a[0]:
			ans = n
			break
		i += 1
	if ans == n:
		print(ans)
	else:
		print(n - cnt)
	t -= 1


tc = int(input())
for j in range(tc):
	n = int(input())
	b = list(map(int, input().rstrip().split()))
	b.sort()
	sm = 0
	flg = 0
	zc = 0
	r = b[0]
	for g in range(n):
		if b[g] == 0:
			zc += 0
		else:
			zc += 1
	if b[0] == 0:
		print(zc)
		continue
	for i in range(1, n):
		if b[i] == r:
			sm += 0
			continue
		if b[i] - r <= r:
			flg = 1
			break
		if b[i] - r > r:
			sm += 1
	if flg == 1:
		print(n)
		continue
	else:
		print(sm)


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	mn1 = a[0]
	mn2 = -1
	freq = 0
	for i in range(n):
		if mn1 != a[i]:
			mn2 = a[i]
			break
		freq += 1
	if mn2 != -1:
		print(n - freq if mn1 * 2 < mn2 else n)
	else:
		print('0')
	return
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mn = min(arr)
	smcnt = arr.count(mn)
	canBe = True
	for i in range(n):
		if arr[i] != mn:
			if arr[i] - 1 >> 1 < mn:
				canBe = False
	if canBe:
		print(n - smcnt)
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = min(arr)
	cnt = 0
	for i in arr:
		if i != m:
			cnt += 1
	for i in arr:
		if i != m and i <= m * 2:
			print(n)
			break
	else:
		print(cnt)


from sys import stdin
import sys
t = int(stdin.readline())
while t > 0:
	t -= 1
	n = int(stdin.readline())
	a = [int(x) for x in stdin.readline().split()]
	ans = 0
	flag = True
	first_min = a[0]
	for i in a:
		if i < first_min:
			first_min = i
	first_min_occurence = 0
	for i in a:
		if i == first_min:
			first_min_occurence += 1
	if first_min == 0 or first_min_occurence == n:
		ans = n - first_min_occurence
	else:
		for i in a:
			if i != first_min and first_min != i % (i - first_min):
				flag = False
				break
	if flag:
		ans = n - first_min_occurence
	else:
		ans = n
	print(ans)


import math
try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		r = min(l)
		c = l.count(r)
		f = 0
		for i in range(0, len(l)):
			if l[i] == r:
				continue
			else:
				y = math.ceil(l[i] / 2) - 1
				if not y >= r:
					f = 1
					break
		if f == 1:
			ans = len(l)
		else:
			ans = len(l) - c
		print(ans)
except:
	pass


import math
T = int(input())
for i in range(T):
	check = 0
	N = int(input())
	A = list(map(int, input().split()))
	small = min(A)
	smallfreq = A.count(small)
	for j in A:
		if j == small:
			continue
		range_j = math.ceil(j / 2) - 1
		if small in range(range_j + 1):
			check = 0
		else:
			check = 1
			break
	if check == 0:
		print(N - smallfreq)
	else:
		print(N)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	s = min(l)
	for i in l:
		if i <= 2 * s and i != s:
			print(n)
			break
	else:
		print(n - l.count(s))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	mini = min(a)
	sts = False
	for i in range(n):
		if a[i] < mini * 2 + 1 and a[i] != mini:
			sts = True
			break
	if sts == False:
		mc = a.count(mini)
		print(n - mc)
	else:
		print(n)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	m = min(seq)
	if any((k % (k - m) != m for k in seq if k != m)):
		print(n)
	else:
		print(n - seq.count(m))


import math, os, io, sys
from collections import Counter
import heapq
from collections import deque

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	n = getInt()
	c = Counter(getList())
	if len(c) == 1:
		return 0
	mn = min(c)
	cnt = c.pop(mn)
	mn2 = min(c)
	if mn2 >= 2 * mn + 1:
		return n - cnt
	else:
		return n
for _ in range(getInt()):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = dict()
	for i in arr:
		d[i] = d.get(i, 0) + 1
	mini = arr[0]
	for i in range(1, len(arr)):
		if mini > arr[i]:
			mini = arr[i]
	cnt = 0
	flag = False
	for i in d:
		if i - mini == 0:
			continue
		elif i % (i - mini) == mini:
			cnt += d[i]
		else:
			flag = True
			break
	if flag:
		print(n)
	else:
		print(cnt)


def fun(arr, n):
	h = {arr[0]: 1}
	sec_min = arr[0]
	mini = arr[0]
	for i in range(1, n):
		if arr[i] in h:
			h[arr[i]] += 1
		else:
			h[arr[i]] = 1
			if arr[i] < mini:
				sec_min = mini
				mini = arr[i]
			elif mini == sec_min:
				sec_min = arr[i]
			elif arr[i] < sec_min:
				sec_min = arr[i]
	if mini == sec_min:
		return 0
	if sec_min > 2 * mini:
		return n - h[mini]
	else:
		return n
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(fun(arr, n))


T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	m = min(l)
	a = 0
	flag = True
	s = 0
	for i in range(N):
		if m == l[i]:
			a += 1
		else:
			b = l[i] - m
			if l[i] % b == m:
				s += 1
			else:
				flag = False
				break
	if flag:
		print(N - a)
	else:
		print(N)


import math
T = int(input())
for i in range(T):
	size = int(input())
	e = [int(e) for e in input().split()]
	minVal = min(e)
	countMin = e.count(minVal)
	flag = False
	for ele in e:
		if ele != minVal:
			if minVal >= 0 and minVal <= math.ceil(ele / 2) - 1:
				continue
			else:
				flag = True
				break
	if flag:
		op = size
	else:
		op = size - countMin
	print(op)


for i in range(int(input())):
	N = int(input())
	arr = [int(i) for i in input().split()]
	Min = min(arr)
	ans = c = 0
	for i in arr:
		if i == Min:
			c += 1
		elif i <= 2 * Min:
			ans = N
	print(ans) if ans == N else print(N - c)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if 0 in a:
		b = a.count(0)
		print(n - b)
	elif 1 in a and 2 in a:
		b = a.count(0)
		print(n - b)
	elif 1 in a and 2 not in a:
		b = a.count(1)
		print(n - b)
	else:
		m = min(a)
		f = 1
		for i in range(n):
			if a[i] != m:
				if a[i] % (a[i] - m) != m:
					f = 0
					break
			if f == 0:
				break
		if f == 1:
			print(n - a.count(m))
		else:
			print(n)


test = int(input())
for i in range(0, test):
	n = int(input())
	lis = list(map(int, input().split()))
	counter = 0
	smalli = 10000000000
	for i in range(0, n):
		if lis[i] < smalli:
			smalli = lis[i]
			counter = 1
		elif lis[i] == smalli:
			counter = counter + 1
	flag = 1
	for j in range(0, n):
		if lis[j] != smalli and lis[j] - smalli <= smalli:
			flag = 0
			break
	if flag or smalli == 0:
		print(n - counter)
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, str(input()).split()))
	ar.sort()
	i = 1
	while i < n and ar[i] == ar[0]:
		i += 1
	cou = i
	ans = n - i
	while i < n:
		if ar[i] <= 2 * ar[0]:
			ans = n
			break
		i += 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dct = dict()
	for x in arr:
		if x in dct:
			dct[x] += 1
		else:
			dct[x] = 1
	b = list(dct.keys())
	if len(b) == 1:
		print(0)
		continue
	if 0 in b:
		print(n - dct[0])
	else:
		flag = 1
		ct = 0
		p = min(b)
		for x in b:
			if x != p:
				if x > 2 * p:
					ct += dct[x]
				else:
					flag = 0
					break
		if flag:
			print(ct)
		else:
			print(n)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(0) > 0:
		x = l.count(0)
		print(n - x)
		continue
	k = l[0]
	for i in range(1, n):
		k = gcd(k, l[i])
	l.sort()
	f = 0
	x = l.count(l[0])
	for i in range(x, n):
		if l[i] <= l[0] * 2:
			f = 1
			break
	if f:
		print(n)
	else:
		print(n - x)


t = int(input())
for z in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		l.sort()
		it = 0
		while it < n and l[it] == l[0]:
			it += 1
		if it < n and l[it] <= 2 * l[0]:
			print(n)
		else:
			print(n - it)


import math

def codechef(n, arr):
	arr.sort()
	mincnt = 0
	for i in range(n):
		if arr[i] == arr[0]:
			mincnt += 1
	if mincnt == n:
		return 0
	res = math.ceil(arr[mincnt] / 2) - 1
	if res < arr[0]:
		ans = n
	else:
		ans = n - mincnt
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(codechef(n, arr))


import math
t = int(input())
while t > 0:
	n = int(input())
	A = list(map(int, input().split(' ')))
	m = min(A)
	c = A.count(m)
	i = 0
	flag = True
	for i in range(n):
		if A[i] == m:
			continue
		if A[i] & 1:
			x = A[i] // 2
		else:
			x = A[i] // 2 - 1
		if x < m:
			flag = False
			print(n)
			break
	if i == n - 1 and flag == True:
		print(n - c)
	t -= 1


import sys
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, sys.stdin.readline().strip().split()))
	if n == 1:
		print(0)
	else:
		for j in range(1, n):
			if a[0] > a[j]:
				(a[0], a[j]) = (a[j], a[0])
		changes_num = 0
		for i in range(1, n):
			if a[0] == a[i]:
				continue
			elif a[0] < 0.5 * a[i]:
				changes_num += 1
			else:
				changes_num = n
				break
		print(changes_num)


import sys, math

def helper(n, arr):
	m = min(arr)
	count = 0
	for i in arr:
		if i == m:
			continue
		elif m < math.ceil(i / 2):
			count += 1
		else:
			return n
	return count
t = int(sys.stdin.readline())
for tt in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	sys.stdout.write(str(helper(n, arr)) + '\n')


import math
test_cases = int(input())
for i in range(0, test_cases):
	n = int(input())
	c = 0
	a = list(map(int, input().split()))
	a.sort()
	b = a[0]
	c = a.count(b)
	flag = 0
	counter = 0
	for j in range(0, len(a)):
		if a[j] == b:
			continue
		elif math.ceil(a[j] / 2) - 1 < b:
			flag = 1
			break
		else:
			counter = counter + 1
	if flag == 1:
		print(len(a))
	else:
		print(counter)


import math
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		minn = min(arr)
		cnt_min = arr.count(minn)
		f = 0
		for i in range(n):
			if arr[i] != minn:
				x = math.ceil(arr[i] / 2) - 1
				if x < minn:
					f = 1
		if f == 1:
			print(n)
		else:
			print(n - cnt_min)
except:
	pass


import math
t = int(input())
for test in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	d = {}
	for i in num:
		if d.get(i) is None:
			d[i] = 1
		else:
			d[i] += 1
	m = min(num)
	c = 0
	for i in num:
		if i != m:
			if m >= 0 and m <= math.ceil(i / 2) - 1:
				c += 1
			else:
				c = n
				break
	if c == n:
		print(c)
	else:
		print(c)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	p = min(li)
	count = 0
	bool = True
	for t in range(len(li)):
		if li[t] == p:
			count += 1
	for i in range(len(li)):
		if li[i] != p:
			if li[i] % (li[i] - p) != p:
				bool = False
				break
			else:
				pass
		else:
			pass
	if bool:
		print(len(li) - count)
	else:
		print(len(li))


t = int(input())
for _ in range(t):
	all = False
	n = int(input())
	arr = [int(x) for x in input().split()]
	m = min(arr)
	c = arr.count(m)
	for i in arr:
		if i == m:
			continue
		elif i <= 2 * m:
			all = True
			break
	if all:
		print(n)
	else:
		print(n - c)


T = int(input())
for tc in range(T):
	n = int(input())
	x = [int(i) for i in input().split()]
	m = min(x)
	d = x.count(m)
	c = True
	for i in x:
		if i == m:
			continue
		elif i <= 2 * m:
			c = False
			break
	if c:
		print(len(x) - d)
	else:
		print(len(x))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	c = min(x)
	s = x.count(c)
	count = 0
	for i in range(n):
		if x[i] == c or x[i] > 2 * c:
			continue
		elif x[i] <= 2 * c:
			count += 1
			break
	if count:
		print(n)
	else:
		print(n - s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = min(a)
	count = 0
	for j in a:
		if j % 2 == 0:
			if j == b:
				pass
			elif j / 2 - 1 < b:
				count = n
				break
			else:
				count += 1
		elif j == b:
			pass
		elif int(j / 2) < b:
			count = n
			break
		else:
			count += 1
	print(count)


from math import ceil
for i in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	minim = min(nums)
	low = False
	for j in range(len(nums)):
		if nums[j] != minim and ceil(nums[j] / 2) - 1 < minim:
			low = True
			break
	if not low:
		print(n - nums.count(minim))
	else:
		print(n)


t = int(input())
while t > 0:
	n = int(input())
	z = list(map(int, input().split()))
	k = min(z)
	lov = 0
	c = 0
	for i in z:
		if i != k:
			if i % 2 == 0:
				f = i // 2 - 1
			else:
				f = i // 2
			if k >= 0 and k <= f:
				c += 1
			else:
				lov = 1
				break
	if lov == 1:
		print(len(z))
	else:
		print(c)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	nums = input()
	nums = nums.split()
	total = 0
	nums2 = []
	epic = 1
	for num in nums:
		nums2.append(int(num))
	nums2.sort()
	start_val = 0
	prev_count = nums2[0]
	for num in nums2:
		if num == prev_count:
			start_val += 1
		elif (num - 1) // 2 >= nums2[0] or num == nums2[0]:
			pass
		else:
			print(N)
			epic = 0
			break
	if epic == 1:
		print(N - start_val)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	mini = min(arr)
	count = c[mini]
	ans = 0
	flag = 0
	for (key, val) in c.items():
		if key == mini:
			continue
		if key % 2 == 0:
			up = key // 2 - 1
		else:
			up = key // 2
		if mini <= up:
			ans += val
		else:
			flag = 1
			break
	if flag:
		print(n)
	else:
		print(ans)


def sol(n, l):
	m = min(l)
	if m == 0:
		return n - l.count(0)
	else:
		for ele in l:
			if ele == m:
				continue
			elif ele <= 2 * m:
				return n
		return n - l.count(m)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(sol(n, l))


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	b = min(a)
	flag = 0
	for j in range(N):
		if a[j] != b and a[j] % (a[j] - b) != b:
			flag = 1
			break
	count = 0
	if flag == 0:
		for j in range(N):
			if a[j] != b:
				count += 1
	else:
		count = N
	print(count)


import math
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	d = Counter(l)
	b = min(l)
	g = 1
	for val in l:
		if val != b:
			a = math.ceil(val / 2) - 1
			if a < b:
				g = 0
				break
	if g == 0:
		print(n)
	else:
		print(n - d[b])


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	min_i = min(arr)
	min_c = 0
	for i in arr:
		if i == min_i:
			min_c += 1
	if min_i == 0:
		print(n - min_c)
	else:
		flag = 0
		for i in arr:
			val = i // 2 - 1 if i % 2 == 0 else i // 2
			if i != min_i and (not 0 <= min_i <= val):
				flag = 1
				break
		if flag:
			print(n)
		else:
			print(n - min_c)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	c = a.count(m)
	r = 0
	for i in range(n):
		if a[i] == m:
			continue
		elif a[i] <= 2 * m:
			r = 1
			break
	if r:
		print(n)
	else:
		print(n - c)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	c = b[0]
	count = 0
	check = 0
	for i in b:
		if i != c:
			if (i + 1) // 2 - 1 >= c:
				count += 1
			else:
				print(a)
				check = 1
				break
	if check == 0:
		print(count)


import numpy as np
o = int(input())
for i in range(o):
	x = int(input())
	y = list(map(int, input().split()))
	z = min(y)
	a = int(np.ceil(z / 2) - 1)
	n = len(y)
	y = [i for i in y if i != z]
	if len(y) == 0:
		print(0)
		continue
	m = min(y)
	b = int(np.ceil(m / 2) - 1)
	if b < z:
		print(n)
	else:
		print(len(y))


t = int(input())

def sp():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=False)
	p = a[0]
	c = 0
	for i in range(1, len(a)):
		if a[i] == p:
			pass
		if p == 0:
			c = len(a) - a.count(0)
			break
		elif a[i] - p == 1:
			c = len(a) - a.count(0)
			break
		elif a[i] - p > 1:
			if a[i] % (a[i] - p) == 0:
				c = len(a) - a.count(0)
				break
			elif a[i] % (a[i] - p) == p:
				c += 1
			elif a[i] % (a[i] - p) != p:
				c = len(a) - a.count(0)
				break
	print(c)
for _ in range(t):
	sp()


import sys
from math import ceil
input = lambda : sys.stdin.readline()
int_arr = lambda : list(map(int, input().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().split())
get_int = lambda : map(int, input().split())
get_flo = lambda : map(float, input().split())
mod = 1000000007

def solve(n, arr):
	mi = min(arr)
	mic = arr.count(mi)
	fg = 1
	for i in range(n):
		if arr[i] != mi:
			if ceil(arr[i] / 2) - 1 < mi:
				fg = 0
				break
	print(n if not fg else n - mic)
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	solve(n, arr)


import math
T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	m = min(A)
	mc = 0
	check = True
	for i in A:
		if i == m:
			mc += 1
		elif math.ceil(i / 2) - 1 >= m:
			continue
		else:
			check = False
	if check:
		print(n - mc)
	else:
		print(n)


import math
for i in range(int(input())):
	l = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	a = [e for e in a if e != m]
	flag = False
	for i in a:
		if m in range(0, math.ceil(i / 2)):
			continue
		else:
			flag = True
			break
	if flag:
		print(l)
	else:
		print(len(a))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	mine = min(a)
	cnt = a.count(mine)
	c = False
	for i in a:
		if i == mine:
			continue
		elif math.ceil(i / 2) - 1 < mine:
			c = True
			break
	if c == True:
		print(n)
	else:
		print(n - cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n > 1:
		l.sort()
		c = 1
		i = 1
		while i < n:
			if l[i] == l[0]:
				i += 1
			else:
				break
		if i == n:
			print('0')
		elif l[0] >= l[i] - l[0]:
			print(n)
		else:
			print(n - i)
	else:
		print(n)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	k = min(l)
	c = 0
	t = 0
	for i in range(len(l)):
		if l[i] == k:
			t = t + 1
			continue
		else:
			r = math.ceil(l[i] / 2) - 1
			if r >= k:
				continue
			else:
				c += 1
	if c > 0:
		print(n)
	else:
		print(n - t)


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	smallest = min(arr)
	count = 0
	for i in arr:
		if i == smallest:
			continue
		if i % 2 == 0:
			if int(i / 2) - 1 < smallest:
				count = -1
				break
		elif int(i / 2) < smallest:
			count = -1
			break
	if count == -1:
		print(n)
	else:
		print(n - arr.count(smallest))


import sys, os.path
from math import gcd, floor, ceil
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = lambda : sys.stdin.readline().replace('\n', '').strip()
tup = lambda typ=int: map(typ, input().split())
lis = lambda typ=int: list(map(typ, input().split()))
pr = lambda n: sys.stdout.write(str(n) + '\n')
prl = lambda n: sys.stdout.write(str(n) + ' ')
for _ in range(int(input())):
	n = int(input())
	l = lis()
	l.sort()
	mi = l[0]
	cnt = l.count(mi)
	f = 0
	for i in range(cnt, n):
		if ceil(l[i] / 2) - 1 < mi:
			f = 1
			break
	if f:
		pr(n)
	else:
		pr(n - cnt)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()[:n]))
	a = min(l)
	for item in l:
		if item <= 2 * a and item != a:
			print(n)
			break
	else:
		print(n - l.count(a))


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	mini = min(array)
	count = 0
	for x in array:
		if x == mini:
			pass
		elif x % (x - mini) == mini:
			count += 1
		else:
			count = len(array) - array.count(0)
			break
	print(count)


import math
t = int(input())
while t:
	flag = 0
	n = int(input())
	l = list(map(int, input().split()))
	minn = min(l)
	p = l.count(minn)
	for i in l:
		if i != minn:
			if math.ceil(i / 2) - 1 < minn:
				print(n)
				flag = 1
				break
	if flag == 0:
		print(n - p)
	t -= 1


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	c = 0
	if m == 0:
		print(n - a.count(m))
		continue
	for i in a:
		if i != m:
			mg = i // 2
			if i % 2 == 0:
				mg -= 1
			if m > mg:
				c = 1
				break
	if c:
		print(n)
	else:
		print(n - a.count(m))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	ans = 0
	f = 0
	mn = min(a)
	mnc = a.count(mn)
	for i in a:
		if i % 2 == 0:
			x = i // 2 - 1
		else:
			x = i // 2
		if x >= 0:
			d[i] = x
		else:
			d[i] = 0
	for i in a:
		if i != mn:
			if mn <= d[i]:
				ans += 1
			else:
				f = 1
				break
	if f:
		ans = n
	print(ans)
	t -= 1