Polycarp found on the street an array $a$ of $n$ elements.

Polycarp invented his criterion for the beauty of an array. He calls an array $a$ beautiful if at least one of the following conditions must be met for each different pair of indices $i \ne j$:

$a_i$ is divisible by $a_j$;

or $a_j$ is divisible by $a_i$.

For example, if:

$n=5$ and $a=[7, 9, 3, 14, 63]$, then the $a$ array is not beautiful (for $i=4$ and $j=2$, none of the conditions above is met);

$n=3$ and $a=[2, 14, 42]$, then the $a$ array is beautiful;

$n=4$ and $a=[45, 9, 3, 18]$, then the $a$ array is not beautiful (for $i=1$ and $j=4$ none of the conditions above is met);

Ugly arrays upset Polycarp, so he wants to remove some elements from the array $a$ so that it becomes beautiful. Help Polycarp determine the smallest number of elements to remove to make the array $a$ beautiful.


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — elements of the array $a$.


-----Output-----

For each test case output one integer — the minimum number of elements that must be removed to make the array $a$ beautiful.


-----Examples-----

Input
4
5
7 9 3 14 63
3
2 14 42
4
45 9 3 18
3
2 2 8
Output
2
0
1
0


-----Note-----

In the first test case, removing $7$ and $14$ will make array $a$ beautiful.

In the second test case, the array $a$ is already beautiful.

In the third test case, removing one of the elements $45$ or $18$ will make the array $a$ beautiful.

In the fourth test case, the array $a$ is beautiful.

Difficulty: HARD
Tags: Number theory

Sorting

Dynamic programming

Mathematics
Skill types: Dynamic programming

Sorting

Starter code:

Solutions:
from sys import stdin
from collections import Counter
input = stdin.readline
for test in range(int(input())):
	n = int(input())
	lst = list(map(int, input().strip().split()))
	N = max(lst) + 1
	po = [0] * N
	cnt = Counter(lst)
	for k in range(1, N):
		po[k] += cnt.get(k, 0)
		for i in range(2 * k, N, k):
			po[i] = max(po[i], po[k])
	print(n - max(po))


for _ in range(int(input())):
	length = int(input())
	array = list(map(int, input().split()))
	array.sort()
	cnt = [0] * (max(array) + 1)
	dp = [0] * (max(array) + 1)
	for x in array:
		cnt[x] += 1
	for i in range(1, len(dp)):
		dp[i] += cnt[i]
		for j in range(i, len(dp), i):
			dp[j] = max(dp[j], dp[i])
	print(length - max(dp))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction
from heapq import *
from random import randint

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		ma = max(a)
		b = Counter(a)
		c = sorted(set(a))
		d = [0] * (ma + 1)
		d[c[-1]] = b[c[-1]]
		ans = b[c[-1]]
		c.pop()
		c.reverse()
		for i in range(len(c)):
			j = 2 * c[i]
			zz = 0
			while j <= ma:
				zz = max(zz, d[j])
				j += c[i]
			d[c[i]] = b[c[i]] + zz
			ans = max(ans, d[c[i]])
		print(n - ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout

def strange_beauty(n, a_a):
	mx = max(a_a)
	dp = [0] * (mx + 1)
	cnt = [0] * (mx + 1)
	r = 0
	for a in a_a:
		cnt[a] += 1
	for i in range(1, mx + 1):
		if cnt[i] == 0:
			continue
		dp[i] += cnt[i]
		j = i * 2
		while j <= mx:
			dp[j] = max(dp[j], dp[i])
			j += i
	for a in a_a:
		r = max(r, dp[a])
	return n - r
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a_a = list(map(int, stdin.readline().split()))
	r = strange_beauty(n, a_a)
	stdout.write(str(r) + '\n')


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		ma = max(a)
		b = [0] * (ma + 1)
		for i in a:
			b[i] += 1
		c = []
		for i in range(1, ma + 1):
			if b[i]:
				c.append(i)
		d = [0] * (ma + 1)
		d[c[-1]] = b[c[-1]]
		ans = b[c[-1]]
		c.pop()
		c.reverse()
		for i in range(len(c)):
			j = 2 * c[i]
			zz = 0
			while j <= ma:
				zz = max(zz, d[j])
				j += c[i]
			d[c[i]] = b[c[i]] + zz
			ans = max(ans, d[c[i]])
		print(n - ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import Counter
cases = int(input())
for _ in range(cases):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	mx = max(arr)
	counts = Counter(arr)
	best = 0
	dp = [0] * (mx + 1)
	for i in range(1, mx + 1):
		if i not in counts:
			continue
		rs = dp[i] + counts[i]
		best = max(best, rs)
		j = i + i
		while j <= mx:
			dp[j] = max(dp[j], rs)
			j += i
	print(n - best)


import sys
import copy
input = sys.stdin.readline
for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0] * (2 * 10 ** 5 + 10)
	cnt2 = [0] * (2 * 10 ** 5 + 10)
	a.sort()
	num10 = -1
	cnt10 = 0
	a2 = []
	for i in range(n):
		if num10 != a[i]:
			if cnt10 != 0:
				a2.append(num10)
				cnt[num10] = cnt10
			cnt10 = 1
			num10 = a[i]
		else:
			cnt10 += 1
	if cnt10 != 0:
		a2.append(num10)
		cnt[num10] = cnt10
	cnt2 = copy.copy(cnt)
	a2.sort()
	for i in range(len(a2)):
		b = a2[i]
		num11 = cnt2[b]
		for j in range(b * 2, 2 * 10 ** 5 + 10, b):
			cnt2[j] = max(cnt2[j], num11 + cnt[j])
	ans = n + 10
	for i in range(len(a2)):
		ans = min(ans, n - cnt2[a2[i]])
	print(ans)


def solve():
	for _ in range(int(input())):
		n = int(input())
		cnt = [0] * 200001
		dp = [0] * 200001
		best = 0
		for a in map(int, input().split()):
			cnt[a] += 1
		for (a, c) in enumerate(cnt):
			if c:
				c += dp[a]
				if best < c:
					best = c
				for i in range(2 * a, 200001, a):
					if dp[i] < c:
						dp[i] = c
		print(n - best)
solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

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

def print_list(l):
	print(' '.join(map(str, l)))
for t in range(N()):
	n = N()
	a = RLL()
	count = [0] * 200001
	for v in a:
		count[v] += 1
	dp = [0] * 200001
	for i in range(1, 200001):
		if count[i] == 0:
			continue
		dp[i] += count[i]
		for j in range(2 * i, 200001, i):
			dp[j] = max(dp[i], dp[j])
	print(n - max(dp))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = [0] * 200001
	for v in arr:
		count[v] += 1
	dp = [0] * 200001
	for i in range(1, 200001):
		if count[i]:
			dp[i] += count[i]
			for j in range(2 * i, 200001, i):
				dp[j] = max(dp[i], dp[j])
	print(n - max(dp))


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = max(l)
	z = [0] * (m + 1)
	f = [0] * (m + 1)
	for i in range(n):
		z[l[i]] += 1
	for i in sorted(set(l)):
		b = i + i
		f[i] += z[i]
		while b <= m:
			f[b] = max(f[b], f[i])
			b += i
	print(n - max(f))


import sys

def solve():
	input = sys.stdin.readline
	MAXN = int(200000.0) + 1
	for t in range(int(input())):
		dp = [0] * MAXN
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		ans = 0
		i = 0
		while i < n:
			v = a[i]
			ii = i + 1
			while ii < n:
				if a[ii] != v:
					break
				ii += 1
			best = dp[v] + ii - i
			for j in range(2 * v, MAXN, v):
				dp[j] = max(dp[j], best)
			ans = max(ans, best)
			i = ii
		print(n - ans)
solve()


factorsMemo = [-1 for _ in range(200001)]

def getAllFactors(x):
	if factorsMemo[x] == -1:
		factors = []
		for i in range(1, int(x ** 0.5) + 1):
			if x % i == 0:
				factors.append(i)
				if x // i != i:
					factors.append(x // i)
		factorsMemo[x] = factors
	return factorsMemo[x]

def main():
	t = int(input())
	allAns = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		a.sort()
		dp = [-inf for _ in range(200001)]
		maxSizeOfBeautifulArray = 0
		for x in a:
			maxPrevCnts = 0
			for f in getAllFactors(x):
				maxPrevCnts = max(maxPrevCnts, dp[f])
			dp[x] = 1 + maxPrevCnts
			maxSizeOfBeautifulArray = max(maxSizeOfBeautifulArray, dp[x])
		allAns.append(n - maxSizeOfBeautifulArray)
	multiLineArrayPrint(allAns)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	cnt = [0 for i in range(mx + 1)]
	dp = [0 for i in range(mx + 1)]
	for i in range(n):
		cnt[a[i]] += 1
	for i in range(1, mx + 1):
		dp[i] += cnt[i]
		for j in range(2 * i, mx + 1, i):
			dp[j] = max(dp[j], dp[i])
	print(n - max(dp))


import sys, math

def main():
	for _ in range(int(sys.stdin.readline().strip())):
		n = int(sys.stdin.readline().strip())
		arr = list(map(int, sys.stdin.readline().strip().split()))
		table = [0] * 200001
		dp = [0] * 200001
		for i in range(n):
			table[arr[i]] += 1
		for i in range(1, 200001):
			dp[i] += table[i]
			if dp[i] > 0:
				for j in range(2 * i, 200001, i):
					dp[j] = max(dp[j], dp[i])
		ans = n - max(dp)
		sys.stdout.write(str(ans) + '\n')
main()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
M = 2 * 10 ** 5 + 1
cnt = [0] * (M + 1)
dp = [0] * (M + 1)
(tc,) = inp()
for _ in range(tc):
	(n,) = inp()
	a = sorted(inp())
	M = max(a)
	for i in range(M + 1):
		cnt[i] = 0
		dp[i] = 0
	for i in a:
		cnt[i] += 1
	for i in range(M, 0, -1):
		for j in range(i, M + 1, i):
			dp[i] = max(dp[i], cnt[i] + dp[j])
	print(n - dp[1])


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
for i in range(int(input())):
	n = int(input())
	alist = list(map(int, input().split()))
	alist.sort()
	maxN = alist[-1] + 1
	anslist = [0] * maxN
	blist = [0] * maxN
	maxans = 0
	for (i, val) in enumerate(alist):
		blist[val] += 1
	for i in range(1, maxN):
		count = anslist[i] + blist[i]
		maxans = max(count, maxans)
		for j in range(2 * i, maxN, i):
			anslist[j] = max(count, anslist[j])
	print(n - maxans)


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def out(var):
	sys.stdout.write(str(var) + '\n')
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = [0] * 200001
	for v in arr:
		count[v] += 1
	dp = [0] * 200001
	for i in range(1, 200001):
		if count[i]:
			dp[i] += count[i]
			for j in range(2 * i, 200001, i):
				dp[j] = max(dp[i], dp[j])
	print(n - max(dp))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
for _ in range(inp()):
	n = inp()
	a = inpl()
	MX = max(a)
	cnt = Counter(a)
	dp = [0] * (MX + 1)
	se = set(a)
	se.discard(1)
	cnt1 = a.count(1)
	li = list(se)
	li.sort()
	for x in li:
		for c in range(2, 10 ** 6):
			now = x * c
			if now > MX:
				break
			if now in se:
				dp[now] = max(dp[now], dp[x] + cnt[x])
	res = cnt1
	for key in list(se):
		res = max(res, dp[key] + cnt[key] + cnt1)
	print(n - res)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import Counter

def divisors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	dp = [0] * int(200000.0 + 1)
	c = Counter(a)
	uniq = sorted(c.keys())
	for i in uniq:
		dp[i] += c[i]
		y = 2 * i
		while y <= 200000.0:
			dp[y] = max(dp[y], dp[i])
			y += i
	print(n - max(dp))


import sys
import math

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod
t = II()
for q in range(t):
	n = II()
	a = LI()
	inf = max(a) + 1
	cnt = [0 for i in range(inf)]
	for i in a:
		cnt[i] += 1
	dp = [0 for i in range(inf)]
	for i in range(1, inf):
		dp[i] += cnt[i]
		for j in range(i * 2, inf, i):
			dp[j] = max(dp[j], dp[i])
	print(n - max(dp))


from collections import Counter
MX = 200001

def solve(arr):
	total = len(arr)
	cnt = [0] * MX
	for a in arr:
		cnt[a] += 1
	u = sorted(set(arr))
	loc = [-1] * MX
	for (i, a) in enumerate(u):
		loc[a] = i
	N = len(u)
	dp = [0] * N
	for (i, a) in enumerate(u):
		dp[i] = max(dp[i], cnt[a])
		for b in range(2 * a, MX, a):
			j = loc[b]
			if j >= 0:
				dp[j] = max(dp[j], dp[i] + cnt[b])
	return total - max(dp)
for _ in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	print(solve(arr))


from sys import stdin
input = stdin.buffer.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	for i in arr:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	l = list(d.keys())
	l.sort()
	m = max(l)
	for i in range(len(l)):
		d[l[i]] = (i, d[l[i]])
	dp = [0] * len(l)
	for i in range(len(l)):
		dp[i] = dp[i] + d[l[i]][1]
		x = 2 * l[i]
		while x <= m:
			if x in d:
				dp[d[x][0]] = max(dp[i], dp[d[x][0]])
			x = x + l[i]
	print(n - max(dp))


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	mv = max(A)
	DP = [0 for i in range(mv + 1)]
	G = {}
	for i in A:
		try:
			G[i] = G[i] + 1
		except:
			G[i] = 1
	for i in range(mv, 0, -1):
		if i in G:
			j = i
			while j <= mv:
				DP[i] = max(DP[i], DP[j] + G[i])
				j = j + i
	print(n - max(DP))


import sys, io, os
from collections import defaultdict
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	A = [*map(int, inp().split())]
	A.sort()
	cnts = defaultdict(int)
	for a in A:
		cnts[a] += 1
	divisors = [0] * 200001
	for (a, c) in cnts.items():
		divisors[a] += c
		for i in range(a, 200001, a):
			divisors[i] = max(divisors[i], divisors[a])
	print(n - max(divisors))


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

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

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
from fractions import Fraction
INF = float('inf')
mod = 10 ** 9 + 7
MAX_SIZE = 100001
isprime = [True] * MAX_SIZE
prime = []
SPF = [None] * MAX_SIZE

def manipulated_seive(N):
	isprime[0] = isprime[1] = False
	for i in range(2, N + 1):
		if isprime[i] == True:
			prime.append(i)
			SPF[i] = i
		j = 0
		while j < len(prime) and i * prime[j] < N and (prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			SPF[i * prime[j]] = prime[j]
			j += 1
manipulated_seive(1000)
for t in range(int(data())):
	n = int(data())
	a = mdata()
	d = dd(int)
	m = max(a)
	l = [0] * (m + 1)
	for i in a:
		d[i] += 1
		l[i] += 1
	for i in range(1, m):
		for j in range(2 * i, m + 1, i):
			l[j] = max(l[j], l[i] + d[j])
	out(n - max(l))


import sys, math
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def main():
	for _ in range(int(sys.stdin.readline().strip())):
		n = int(sys.stdin.readline().strip())
		arr = list(map(int, sys.stdin.readline().strip().split()))
		table = [0] * 200001
		dp = [0] * 200001
		for i in range(n):
			table[arr[i]] += 1
		for i in range(1, 200001):
			dp[i] += table[i]
			if dp[i] > 0:
				for j in range(2 * i, 200001, i):
					dp[j] = max(dp[j], dp[i])
		ans = n - max(dp)
		sys.stdout.write(str(ans) + '\n')
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	dp = [0] * (arr[-1] + 1)
	c = [0] * (arr[-1] + 1)
	for i in range(1, n + 1):
		c[arr[i - 1]] += 1
	for i in range(1, arr[-1] + 1):
		dp[i] += c[i]
		j = 2 * i
		while j <= arr[-1]:
			dp[j] = max(dp[j], dp[i])
			j += i
	print(n - max(dp))


from collections import Counter

def f(arr):
	cnt = Counter(arr)
	mxn = max(arr) + 100
	factor = [0] * mxn
	for i in range(1, len(factor)):
		factor[i] += cnt.get(i, 0)
		for j in range(2 * i, mxn, i):
			factor[j] = max(factor[i], factor[j])
	return len(arr) - max(factor)
for i in range(int(input())):
	s = input()
	lst = list(map(int, input().strip().split()))
	print(f(lst))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	table = [0] * (mx + 1)
	for x in a:
		table[x] += 1
	dp = [0] * (mx + 1)
	for x in range(mx, 0, -1):
		if table[x] == 0:
			continue
		dp[x] = table[x]
		for y in range(x + x, mx + 1, x):
			dp[x] = max(dp[x], dp[y] + table[x])
	print(N - max(dp))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = sorted(map(int, input().split()))
	m = max(A)
	cnt = [0] * (m + 1)
	for a in A:
		cnt[a] += 1
	dp = [0] * (m + 1)
	for a in sorted(set(A)):
		dp[a] += cnt[a]
		b = a + a
		while b <= m:
			dp[b] = max(dp[b], dp[a])
			b += a
	print(n - max(dp))


import sys
input = sys.stdin.readline
from collections import Counter
MAX = 2 * 10 ** 5
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * (MAX + 1)
	count = Counter(a)
	uniqs = sorted(count.keys())
	for x in uniqs:
		dp[x] += count[x]
		y = 2 * x
		while y <= MAX:
			dp[y] = max(dp[x], dp[y])
			y += x
	print(n - max(dp))


from collections import *
from bisect import *
import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	v = set()
	dp = [0] * 200001
	f = Counter(a)
	a.sort()
	for i in a:
		if i in v:
			continue
		v.add(i)
		dp[i] += f[i]
		b = 2 * i
		while b <= a[-1]:
			dp[b] = max(dp[b], dp[i])
			b += i
	print(n - max(dp))


from sys import stdin, stdout
import math
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if not n % i)))

def main():
	sav = [0 for _ in range(200001)]
	for _ in range(int(stdin.readline())):
		n = int(stdin.readline())
		arr = list(map(int, stdin.readline().split()))
		arr.sort()
		mx_val = arr[-1]
		dp = [0 for _ in range(mx_val + 1)]
		mx = 0
		for (i, x) in enumerate(arr):
			if x == 1:
				dp[1] += 1
				continue
			if i > 0 and arr[i - 1] == x:
				dp[x] += 1
				mx = max(dp[x], mx)
				continue
			if sav[x] == 0:
				sav[x] = factors(x)
				sav[x].remove(1)
				sav[x].remove(x)
			for y in sav[x]:
				dp[x] = max(dp[y], dp[x])
			dp[x] += 1
			mx = max(dp[x], mx)
		ans = n - mx - dp[1]
		stdout.write(str(ans) + '\n')
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	(b, c) = ([0] * (mx + 1), [0] * (mx + 1))
	for i in a:
		b[i] += 1
	for k in range(1, mx + 1):
		c[k] += b[k]
		for j in range(2 * k, mx + 1, k):
			c[j] = max(c[j], c[k])
	print(n - max(c))


import sys
input = sys.stdin.buffer.readline
from math import gcd
for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	C = [0] * 200001
	for i in range(N):
		C[A[i]] += 1
	DP = [0] * 200001
	for i in range(200000, 0, -1):
		if C[i] == 0:
			DP[i] = -10000000
			continue
		DP[i] = C[i]
		for j in range(i * 2, 200001, i):
			DP[i] = max(DP[i], DP[j] + C[i])
	P = 0
	for i in range(N):
		if P < DP[A[i]]:
			P = DP[A[i]]
	print(N - P)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def f(x):
	d[a[-1]] -= 1
	d[a[x]] -= 1
	res.append([a[-1], a[x]])
	last = a[-1]
	for i in range(2 * n - 2, -1, -1):
		if d[a[i]] > 0:
			d[a[i]] -= 1
			if d[last - a[i]] > 0:
				d[last - a[i]] -= 1
				res.append([a[i], last - a[i]])
				last = a[i]
			else:
				return False
	return True
t = N()
for i in range(t):
	n = N()
	a = RLL()
	c = Counter(a)
	ans = 0
	ma = max(a)
	dp = [0] * (ma + 1)
	for i in range(ma, 1, -1):
		if i not in c:
			continue
		cur = 0
		j = i * 2
		while j <= ma:
			cur = max(cur, dp[j])
			j += i
		dp[i] = cur + c[i]
		ans = max(ans, dp[i])
	if 1 in c:
		ans += c[1]
	print(n - ans)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)
for _ in range(int(input())):
	n = int(input())
	A = sorted(map(int, input().split()))
	m = max(A)
	cnt = [0] * (m + 1)
	for a in A:
		cnt[a] += 1
	dp = [0] * (m + 1)
	for a in sorted(set(A)):
		dp[a] += cnt[a]
		b = a + a
		while b <= m:
			dp[b] = max(dp[b], dp[a])
			b += a
	print(n - max(dp))


import sys
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = max(arr) + 1
	dp = [0] * m
	cnt = [0] * m
	for i in range(len(arr)):
		cnt[arr[i]] += 1
	for i in range(1, m):
		dp[i] += cnt[i]
		for j in range(2 * i, m, i):
			dp[j] = max(dp[i], dp[j])
	print(n - max(dp))


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
for i in range(int(input())):
	n = int(input())
	alist = list(map(int, input().split()))
	maxN = int(200000.0 + 1)
	anslist = [0] * maxN
	blist = [0] * maxN
	for (i, val) in enumerate(alist):
		blist[val] += 1
	for i in range(1, maxN):
		if blist[i] == 0:
			continue
		anslist[i] += blist[i]
		for j in range(2 * i, maxN, i):
			anslist[j] = max(anslist[i], anslist[j])
	print(n - max(anslist))