You are given $\mbox{Q}$ queries. Each query consists of a single number $N$. You can perform any of the $2$ operations on $N$ in each move:

1: If we take 2 integers $\class{ML__boldsymbol}{\boldsymbol{a}}$ and $\boldsymbol{b}$ where $N=a\times b$ $(a\neq1$, $b\neq1)$, then we can change $N=max(a,b)$

2: Decrease the value of $N$ by $1$. 

Determine the minimum number of moves required to reduce the value of $N$ to $0$.

Input Format

The first line contains the integer $Q$. 

The next $Q$ lines each contain an integer, $N$.  

Constraints

$1\leq Q\leq10^3$ 

$0\leq N\leq10^6$  

Output Format

Output $Q$ lines. Each line containing the minimum number of moves required to reduce the value of $N$ to $0$.

Sample Input
2
3
4

Sample Output
3
3

Explanation

For test case 1, We only have one option that gives the minimum number of moves. 

Follow $3$ -> $2$ -> $\mbox{1}$ -> $0$. Hence, $3$ moves.

For the case 2, we can either go $\begin{array}{c}4\end{array}$ -> $3$ -> $2$ -> $1$ -> $0$ or $\begin{array}{c}4\end{array}$ -> $2$ -> $1$ -> $0$. The 2nd option is more optimal. Hence, $3$ moves.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import math
import time
start = time.time()

def Sol(N):
	if N == 0:
		return 0
	Q = [(N, 0)]
	setQ = [0] * N
	while Q:
		(N, steps) = Q.pop(0)
		if N == 1:
			return steps + 1
		div = int(math.sqrt(N))
		while div > 1:
			if N % div == 0 and (not setQ[N // div]):
				Q.append((N // div, steps + 1))
				setQ[N // div] = 1
			div -= 1
		if not setQ[N - 1]:
			Q.append((N - 1, steps + 1))
			setQ[N - 1] = 1
Q = int(input())
for _ in range(Q):
	N = int(input())
	print(Sol(N))


from collections import deque

def solve(n):
	if n == 0:
		return 0
	Q = deque([-1, n])
	seen = set()
	moves = 0
	while Q:
		n = Q.popleft()
		if n == -1:
			moves += 1
			n = Q.popleft()
			Q.append(-1)
		if n == 1:
			return moves
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				f = n // i
				if f not in seen:
					Q.append(f)
					seen.add(f)
		if n - 1 not in seen:
			Q.append(n - 1)
			seen.add(n - 1)
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


import math

def Sol(N):
	if N == 0:
		return 0
	Q = [(N, 0)]
	setQ = [0] * N
	while Q:
		(N, steps) = Q.pop(0)
		if N == 1:
			return steps + 1
		div = int(math.sqrt(N))
		while div > 1:
			if N % div == 0 and (not setQ[N // div]):
				Q.append((N // div, steps + 1))
				setQ[N // div] = 1
			div -= 1
		if not setQ[N - 1]:
			Q.append((N - 1, steps + 1))
			setQ[N - 1] = 1
Q = int(input())
for _ in range(Q):
	N = int(input())
	print(Sol(N))


from math import floor, ceil, sqrt

def go(ns):
	max_n = max(ns)
	visited = [10000000000.0 for i in range(max_n + 1)]
	start = 2
	for i in range(0, min(len(visited), start)):
		visited[i] = i
	for i in range(start, max_n + 1):
		mn = min(visited[i - 1] + 1, visited[i], i)
		visited[i] = mn
		j = 2
		while j <= i:
			m = i * j
			if m > max_n:
				break
			visited[m] = min(visited[m], mn + 1)
			j += 1
	for n in ns:
		print(visited[n])
q = int(input())
ns = [int(input()) for i in range(q)]
go(ns)


from collections import deque

def f(val):
	return ((i, int(val / i)) for i in range(2, int(val ** 0.5) + 1) if val % i == 0)

def num_steps(n):
	if n == 0:
		return 0
	visited = set()
	queue = deque()
	queue.append((n, 0))
	while queue:
		(n, d) = queue.popleft()
		for (a, b) in f(n):
			new_n = max(a, b)
			if new_n not in visited:
				queue.append((new_n, d + 1))
				visited.add(new_n)
		if n - 1 not in visited:
			queue.append((n - 1, d + 1))
			visited.add(n - 1)
		if n - 1 == 0:
			return d + 1
t = int(input().strip())
for _ in range(t):
	print(num_steps(int(input().strip())))


d = list(range(1000001))
for i in range(1000000):
	d[i + 1] = min(d[i + 1], d[i] + 1)
	j = 2
	while j <= i and j * i <= 1000000:
		d[i * j] = min(d[i] + 1, d[i * j])
		j += 1
for _ in range(int(input())):
	print(d[int(input())])


import sys
import math

def solve(N):
	if N == 0:
		return 0
	seem = set()
	queue = []
	queue.append((N, 0))
	while len(queue) > 0:
		(n, steps) = queue.pop(0)
		if n in seem:
			continue
		seem.add(n)
		if n == 1:
			return steps + 1
		queue.append((n - 1, steps + 1))
		sqrtn = math.floor(math.sqrt(n))
		for x in range(2, sqrtn + 1):
			if n % x == 0:
				queue.append((n // x, steps + 1))
	return False
Q = int(sys.stdin.readline())
for q in range(Q):
	N = int(sys.stdin.readline())
	print(solve(N))


def f(N):
	i = 0
	Q = [(N, 0)]
	S = set()
	while Q:
		(n, d) = Q[i]
		i += 1
		if n == 0:
			return d
		for k in range(2, int(n ** 0.5) + 1):
			if n % k == 0:
				m = max(k, n // k)
				if m not in S:
					Q.append((m, d + 1))
					S.add(m)
		if n - 1 not in S:
			Q.append((n - 1, d + 1))
			S.add(n - 1)
Q = int(input())
for q in range(Q):
	N = int(input())
	print(f(N))


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


import math
import time
start = time.time()

def Sol(N):
	if N == 0:
		return 0
	Q = [(N, 0)]
	setQ = [0] * N
	while Q:
		(N, steps) = Q.pop(0)
		if N == 1:
			return steps + 1
		div = int(math.sqrt(N))
		while div > 1:
			if N % div == 0 and (not setQ[N // div]):
				Q.append((N // div, steps + 1))
				setQ[N // div] = 1
			div -= 1
		if not setQ[N - 1]:
			Q.append((N - 1, steps + 1))
			setQ[N - 1] = 1
Q = int(input())
for _ in range(Q):
	N = int(input())
	print(Sol(N))


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


from collections import deque
q = int(input())
arr = []
for _ in range(q):
	arr.append(int(input()))
size = max(arr)
cost = [None] * (size + 1)
order = deque()
cost[0] = 0
cost[1] = 1
order.append((1, cost[1]))
while order:
	(i, c) = order.popleft()
	if i + 1 <= size and cost[i + 1] is None:
		cost[i + 1] = c + 1
		order.append((i + 1, c + 1))
	for j in range(2, i + 1):
		if j * i > size:
			break
		if cost[j * i] is None:
			cost[j * i] = c + 1
			order.append((j * i, c + 1))
for num in arr:
	print(cost[num])


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


def getMinimumMoveUnder(N):
	moves = list(range(N))
	for m in range(2, N):
		moves[m] = min(moves[m], moves[m - 1] + 1)
		for l in range(m * 2, min(m * m + 1, N), m):
			moves[l] = min(moves[l], moves[m] + 1)
	return moves
Q = int(input())
Ns = list((int(input()) for _ in range(Q)))
moves = getMinimumMoveUnder(max(Ns) + 1)
for n in Ns:
	print(moves[n])


from math import *
moves = {0: 0, 1: 1, 2: 2, 3: 3}

def getMoves(n, x):
	if n in moves:
		return moves[n]
	if ceil(log(log(n, 2), 2)) + 2 > x:
		return n
	i = int(n ** 0.5)
	minMoves = n
	while i > 1:
		if n % i == 0:
			minMoves = min(minMoves, 1 + getMoves(n // i, n))
		i -= 1
	if minMoves == n:
		minMoves = 1 + getMoves(n - 1, n)
	else:
		minMoves = min(minMoves, 1 + getMoves(n - 1, minMoves - 2))
	moves[n] = minMoves
	return minMoves
q = int(input())
for i in range(q):
	n = int(input())
	print(getMoves(n, n))


from datetime import datetime
startTime = datetime.now()

def gen(n):
	lst = [100] * (n + 1)
	lst[0] = 0
	for i in range(1, n + 1):
		lst[i] = lst[i - 1] + 1
	ite = 4
	while ite > 0:
		for i in range(2, n // 2 + 1):
			for j in range(i, n // 2 + 1):
				if i * j > n:
					break
					pass
				if lst[j] + 1 < lst[i * j] and lst[j] < lst[i * j - 1]:
					lst[i * j] = lst[j] + 1
					pass
		for i in range(2, n + 1):
			if lst[i] > lst[i - 1] + 1:
				lst[i] = lst[i - 1] + 1
		ite -= 1
	return lst
q = int(input().strip())
inputs = []
maxV = -1
for i in range(q):
	ar = int(input())
	if ar > maxV:
		maxV = ar
	inputs.append(ar)
list_sol = gen(maxV)
for i in range(q):
	print(list_sol[inputs[i]])


def get_list(n):
	lst = [[] for _ in range(n + 1)]
	(lst[0], lst[1]) = (0, 1)
	for i in range(2, n + 1):
		if lst[i]:
			lst[i] = min(lst[i])
		else:
			lst[i] = lst[i - 1] + 1
		num_moves = lst[i] + 1
		if i < n:
			lst[i + 1].append(num_moves)
		j = 2
		p = i * j
		while p < n + 1 and j <= i:
			lst[p].append(num_moves)
			j += 1
			p = i * j
	return lst
q = int(input().strip())
lst = []
for _ in range(q):
	lst.append(int(input().strip()))
nums = get_list(max(lst))
for i in lst:
	print(nums[i])


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


from math import sqrt

def getPaths(n, cache={}):
	if n not in cache:
		cache[n] = set([max(n // i, i) for i in range(2, int(sqrt(n)) + 1, 1) if n % i == 0] + [n - 1])
	return cache[n]

def solve(n):
	steps = -1
	paths = set([n])
	found = False
	while not found:
		steps += 1
		newPaths = set()
		for path in paths:
			if path == 0:
				found = True
				break
			elif path == 2:
				found = True
				steps += 2
				break
			newPaths |= getPaths(path)
		paths = newPaths
	return steps
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


from collections import deque
from math import sqrt

def factors(n):
	step = 2 if n % 2 else 1
	for a in range(1, int(sqrt(n)) + 1, step):
		if n % a == 0:
			yield (a, n // a)

def neighbors(n):
	yield (n - 1)
	for (factor_a, factor_b) in factors(n):
		yield factor_b

def bfs(n):
	to_try = deque([(n, 0)])
	tried = set()
	while to_try:
		(trying_n, trying_moves) = to_try.popleft()
		if trying_n == 0:
			return trying_moves
		if trying_n not in tried:
			for neighbor in neighbors(trying_n):
				if neighbor not in tried:
					to_try.append((neighbor, trying_moves + 1))
		tried.add(trying_n)
for _ in range(int(input())):
	print(bfs(int(input())))


import math

def calc_steps(n):
	q = [n]
	steps = 0
	seen = set()
	while q:
		if 0 in q:
			return steps
		nq = []
		for ni in q:
			nq += [max(i, ni // i) for i in range(2, math.floor(math.sqrt(ni)) + 1) if ni % i == 0]
			nq.append(ni - 1)
		nq = set(nq)
		q = list(nq - seen)
		seen |= nq
		steps += 1
for _ in range(int(input().strip())):
	print(calc_steps(int(input().strip())))


nmax = 10 ** 6
sqrt_nmax = 10 ** 3
half_nmax = nmax // 2
cache = list(range(nmax + 1))
for n in range(2, sqrt_nmax + 1):
	c = cache[n] + 1
	for m in range(2 * n, n * n + 1, n):
		cache[m] = min(cache[m], c)
	cache[n + 1] = min(cache[n + 1], c)
for n in range(sqrt_nmax + 1, half_nmax + 1):
	c = cache[n] + 1
	for m in range(2 * n, nmax + 1, n):
		cache[m] = min(cache[m], c)
	cache[n + 1] = min(cache[n + 1], c)
for n in range(half_nmax + 1, nmax + 1):
	cache[n] = min(cache[n - 1] + 1, cache[n])
nq = int(input())
for _ in range(nq):
	n = int(input())
	print(cache[n])


Q = int(input().strip())
queries = []
for i in range(Q):
	queries.append(int(input().strip()))
max_q = max(queries)
best_moves = [None for i in range(max_q + 2)]
best_moves[0] = 0
best_moves[1] = 1
for i in range(1, max_q + 1):
	potential = best_moves[i] + 1
	for j in range(2 * i, min(max_q + 1, i ** 2 + 1), i):
		best_moves[j] = min(best_moves[j], potential) if best_moves[j] else potential
	best_moves[i + 1] = min(best_moves[i + 1], potential) if best_moves[i + 1] else potential
for q in queries:
	print(best_moves[q])


import math
tab = [0] * 1000001
mul = [-1] * 1000001
primes = []
last = 1
lastM = 5

def findPrimes():
	N = 1000000
	p = 2
	n = int(math.sqrt(N))
	while p < n:
		m = N // p
		a = 2
		while a <= m:
			mul[a * p] = 1
			a += 1
		p = p + 1
		while p < n:
			if mul[p] == -1:
				break
			p += 1
	for i in range(2, n):
		if mul[i] == -1:
			primes.append(i)
			mul[i] = None
	mul[0] = None
	mul[1] = None

def findMul(n):
	if mul[n] == None:
		return
	for p in primes:
		if n % p == 0:
			break
	q = n // p
	dq = mul[q]
	dp = set()
	if dq == None:
		dp.add(max(p, q))
	else:
		for item in dq:
			a = item * p
			b = q // item
			if max(a, b) not in dp:
				dp.add(max(a, b))
			a = item
			b = q // item * p
			if max(a, b) not in dp:
				dp.add(max(a, b))
			a = p
			b = q
			if max(a, b) not in dp:
				dp.add(max(a, b))
	mul[n] = dp
	lastM = n + 1

def findDownToZero(n):
	if mul[n] == None:
		tab[n] = tab[n - 1] + 1
		return
	steps = 1000000
	dn = mul[n]
	for item in dn:
		a = int(item)
		steps = min(tab[a] + 1, steps)
	steps = min(tab[n - 1] + 1, steps)
	tab[n] = steps
	last = n + 1

def downToZero(n):
	if n < last:
		return tab[n]
	for i in range(lastM, n + 1):
		findMul(i)
	for i in range(last, n + 1):
		findDownToZero(i)
	return tab[n]
Q = int(input().strip())
findPrimes()
divisorMemo = [-1] * 1000001

def findLargeDivisors(n):
	if divisorMemo[n] != -1:
		return divisorMemo[n]
	l = []
	s = int(math.sqrt(n))
	for a in reversed(range(2, s + 1)):
		if n % a == 0:
			l.append(n // a)
	divisorMemo[n] = l
	return l

def bfsDownToZero(n):
	if n == 0:
		return 0
	currentQ = set()
	nextQ = set()
	steps = 0
	currentQ.add(n)
	while currentQ:
		a = currentQ.pop()
		if a == 0:
			return steps
		l = findLargeDivisors(a)
		for d in l:
			nextQ.add(d)
		nextQ.add(a - 1)
		if not currentQ:
			currentQ = nextQ
			nextQ = set()
			steps += 1
	return steps
for i in range(Q):
	n = int(input().strip())
	p = bfsDownToZero(n)
	print(p)


MAX_N = 1000000
sqrt = int(MAX_N ** 0.5)
steps = [i for i in range(MAX_N + 1)]
for i in range(1, MAX_N + 1):
	steps[i] = min(steps[i], steps[i - 1] + 1)
	for j in range(2, sqrt + 1):
		if j > i:
			break
		mul = j * i
		if mul > MAX_N:
			break
		steps[mul] = min(steps[mul], steps[i] + 1)
for _ in range(int(input())):
	print(steps[int(input())])


import math

def run(N):
	if N <= 2:
		return N
	visited = set()
	queue = []

	def try_visit(number, step):
		if number not in visited:
			visited.add(number)
			queue.append((number, step))
	try_visit(N, 0)
	while queue:
		(number, step) = queue.pop(0)
		step += 1
		try_visit(number - 1, step)
		for a in range(2, int(math.sqrt(number)) + 1):
			if number % a == 0:
				try_visit(max(a, number // a), step)
		if 0 in visited:
			return step
	return None
for _ in range(int(input())):
	print(run(int(input())))


ar = tuple((int(input()) for _ in range(int(input()))))
n = max(ar) + 1
val = [0, 1] + [n] * (n - 2)
for i in range(2, n):
	if val[i] > val[i - 1] + 1:
		val[i] = val[i - 1] + 1
	p = val[i] + 1
	for j in range(i << 1, min(i * i + 1, n), i):
		if val[j] > p:
			val[j] = p
print(*map(val.__getitem__, ar), sep='\n')


import math, sys
N = 1000000
primes = [True] * N
primes[0] = primes[1] = False
for (i, isprime) in enumerate(primes):
	if isprime:
		for n in range(i * i, N, i):
			primes[n] = False
j = 3
c = [3, 4]
d = [0] * N
d[:5] = [0, 1, 2, 3, 3]

def get(c0, j):
	j += 1
	get.c = []
	for i in c0:
		for k in range(i, 1, -1):
			update(i * k, j)
		update(i + 1, j)
	return (get.c, j)

def update(x, j):
	if x < N and (not d[x]):
		get.c.append(x)
		d[x] = j
(c, j) = get(c, j)
(c, j) = get(c, j)
(c, j) = get(c, j)
(c, j) = get(c, j)

def calc(n, j):
	if n == 0 or d[n] != 0:
		return d[n]
	p = None
	if not primes[n]:
		n0 = n
		for a in range(int(math.floor(math.sqrt(n0))), 1, -1):
			if n0 % a == 0:
				f = int(n0 / a)
				d[f] = calc(f, j + 1)
				if p is None or d[f] < p:
					p = d[f]
	f = int(n - 1)
	d[f] = calc(f, j + 1)
	if p is None or d[f] < p:
		p = d[f]
	return 1 + p
q = int(input())
for i in range(q):
	n = int(input())
	print(calc(n, 0))


import collections
steps = [0, 1, 2] + [10 ** 7] * 10 ** 6
q = collections.deque([2])
while q:
	x = q.popleft()
	if x <= 10 ** 6 and steps[x + 1] > steps[x] + 1:
		steps[x + 1] = steps[x] + 1
		q.append(x + 1)
	for i in range(2 * x, min(10 ** 6, x * x) + 1, x):
		if steps[i] > steps[x] + 1:
			steps[i] = steps[x] + 1
			q.append(i)
for i in range(int(input())):
	print(steps[int(input())])


import math
n = int(input())
for i in range(n):
	memoize = set()
	count = 0
	n = int(input())
	queue = []
	queue.append((n, count))
	while len(queue):
		(data, count) = queue.pop(0)
		if data <= 1:
			if data == 1:
				count += 1
			break
		if data - 1 not in memoize:
			memoize.add(data - 1)
			queue.append((data - 1, count + 1))
		sqr = int(math.sqrt(data))
		for i in range(sqr, 1, -1):
			if data % i == 0:
				div = max(int(data / i), i)
				if div not in memoize:
					memoize.add(div)
					queue.append((div, count + 1))
	print(count)


import math
n = int(input())

def calculate(answerA, q):
	min = q
	index = int(q)
	if answerA[index] == 0:
		steps = 0
		maxSteps = 5
		while steps < maxSteps or min == q:
			firstGuess = math.floor(math.sqrt(q))
			for i in range(firstGuess, 1, -1):
				if q % i == 0:
					test = q / i
					temp = steps + 1 + calculate(answerA, math.ceil(q / i))
					if temp < min:
						min = temp
			steps += 1
			q -= 1
			if q < 2:
				min = min if min < index or index == 1 else steps + 1
				break
		answerA[index] = min
	return answerA[index]
answerArray = [0] * (pow(10, 6) + 1)
for i in range(n):
	q = int(input())
	if q == 0:
		print('0')
	else:
		print(calculate(answerArray, q))


import collections
import math
Q = int(input())
q_curr = collections.deque([])
q_next = collections.deque([])
processed = {}
for _ in range(Q):
	q_curr.clear()
	q_next.clear()
	processed.clear()
	N = int(input())
	q_curr.append(N)
	processed[N] = 1
	d = 0
	while True:
		if not q_curr:
			q_curr = q_next
			q_next = collections.deque([])
			d = d + 1
		e = q_curr.popleft()
		if e <= 1:
			print(d + e)
			break
		else:
			if e - 1 not in processed:
				q_next.append(e - 1)
				processed[e - 1] = 1
			for i in range(int(math.sqrt(e)), 1, -1):
				if e % i == 0 and e // i not in processed:
					k = e // i
					q_next.append(k)
					processed[k] = 1


from math import sqrt
maxInt = 1000001
stepsTo = list(range(maxInt))
stepsTo[0] = 0
for i in range(1, maxInt):
	stepsTo[i] = min(stepsTo[i], stepsTo[i - 1] + 1)
	for j in range(2, i + 1):
		if j * i >= maxInt:
			break
		stepsTo[j * i] = min(stepsTo[j * i], stepsTo[i] + 1)
for _ in range(int(input().strip())):
	n = int(input().strip())
	print(stepsTo[n])


import math
from collections import deque
global_cache = {}

def findMinMoves(n):
	queue = deque([n])
	next = []
	moves = 0
	cache = {}
	while len(queue) > 0:
		current = queue.popleft()
		if current == 0:
			return moves
		if current not in cache:
			next += getGreaterFactors(current)
			next.append(current - 1)
			cache[current] = True
		if len(queue) == 0 and len(next) > 0:
			queue.extend(next)
			next = []
			moves += 1

def getGreaterFactors(n):
	greaterFactors = []
	for i in range(math.floor(math.sqrt(n)), 1, -1):
		if n % i == 0:
			greaterFactors.append(int(n / i))
	return greaterFactors
queries = int(input())
for i in range(queries):
	n = int(input())
	print(findMinMoves(n))


limit = 10 ** 6 + 2
counts = [0] * limit
counts[1] = 1
cur = 0
changed = True
while changed:
	cur += 1
	changed = False
	for ix in range(1, limit - 1):
		if counts[ix] == cur:
			if counts[ix + 1] == 0:
				counts[ix + 1] = cur + 1
				changed = True
			for val in range(ix, ix * ix + 1, ix):
				if val >= limit:
					break
				if counts[val] == 0:
					counts[val] = cur + 1
					changed = True
Q = int(input())
for q in range(Q):
	N = int(input())
	print(counts[N])


from math import sqrt, floor

def n_steps(N):
	if N == 0:
		return 0
	nsteps = 0
	q = set([N])
	while True:
		qnew = set()
		nsteps += 1
		for ci in q:
			for c in candidates(ci):
				if c == 0:
					return nsteps
				qnew.add(c)
		q = qnew

def candidates(N):
	yield (N - 1)
	for a in range(2, floor(sqrt(N) + 1)):
		if not N % a:
			b = N // a
			yield b
q = int(input())
for _ in range(q):
	n = int(input())
	print(n_steps(n))


import collections
lim = 10 ** 6 + 1
dist = [0] * lim
active = collections.deque()
active.append(0)
while active:
	n = active.popleft()
	d = dist[n] + 1
	x = n + 1
	if x < lim and dist[x] == 0:
		dist[x] = d
		active.append(x)
	for m in range(2, n + 1):
		x = m * n
		if x >= lim:
			break
		if dist[x] == 0:
			dist[x] = d
			active.append(x)
Q = int(input())
for q in range(Q):
	N = int(input())
	print(dist[N])


import sys
import math
PrintDebug = False
PrintPath = False
DebugEntries = set()
Factors = {}
Encountered = {}
UpperLimit = 0
NextMinimalDownstep = {2: 1, 1: 0}

def calc_factors(n):
	if n in Factors:
		return Factors[n]
	factor_list = []
	top_factor = int(math.sqrt(n))
	for fact in reversed(range(2, top_factor + 1)):
		(fact_2, rem) = divmod(n, fact)
		if rem == 0 and fact_2 > 1 and (fact > 1):
			max_factor = max(fact, fact_2)
			min_factor = min(fact, fact_2)
			factor_list.append((max_factor, min_factor))
	if len(factor_list) > 0:
		Factors[n] = factor_list
	else:
		Factors[n] = None
	return Factors[n]

def prune_factors(n, max_factor):
	if len(Factors[n]) <= 1:
		return
	for (factor1, factor2) in Factors[n]:
		if factor1 != max_factor:
			continue
		Factors[n] = [(factor1, factor2)]
		return
	assert False

def resolve_n(n, step_number):
	if n <= 3:
		return n - 1
	factor_list = calc_factors(n)
	if factor_list != None:
		for f_tuple in factor_list:
			return f_tuple[0]
	return n - 1

def iterative_step_down(n):
	num_steps = 0
	while n > 0:
		n = resolve_n(n, num_steps + 1)
		num_steps += 1
	return num_steps

def generate(n, step=0, limit_steps=-1):
	if n == 0:
		return None
	if limit_steps == -1:
		limit_steps = iterative_step_down(n) + 2
	if n in DebugEntries:
		print('(debug-entries) case: generate(): %s, %s, %s' % (n, step, limit_steps))
	if n in NextMinimalDownstep:
		suffix_values = []
		suffix_values.append(n)
		while n > 1:
			n = NextMinimalDownstep[n]
			suffix_values.append(n)
		return suffix_values
	if step >= limit_steps:
		return None
	results = []
	recurse_list = []
	factor_list = calc_factors(n)
	if factor_list != None:
		for f_tuple in factor_list:
			fact_max = f_tuple[0]
			recurse_list.append(fact_max)
	recurse_list.append(n - 1)
	inadequate_results = False
	for next_n in recurse_list:
		if n in DebugEntries:
			print('invoking generate(%s, %s, %s)' % (next_n, step + 1, limit_steps))
		sub_result = generate(next_n, step + 1, limit_steps)
		if sub_result != None:
			results.append([n] + sub_result)
		else:
			inadequate_results = True
			if n in DebugEntries:
				print('inadequate results for n, next_n = %s, %s' % (n, next_n))
	if len(results) == 0:
		return None
	shortest_path = results[0]
	for res in results:
		if n in DebugEntries:
			print('all results: path = %s' % str(res))
		if len(res) < len(shortest_path):
			shortest_path = res
	if not inadequate_results:
		for i in range(len(shortest_path)):
			if i + 1 < len(shortest_path):
				if shortest_path[i] not in NextMinimalDownstep:
					NextMinimalDownstep[shortest_path[i]] = shortest_path[i + 1]
	if PrintDebug:
		print('shortest_path = %s' % str(shortest_path))
	return shortest_path

def process_input():
	num_queries = int(input())
	for i in range(num_queries):
		n = int(input())
		permute = generate(n)
		if permute == None:
			print(0)
		else:
			print(len(permute))
		if PrintPath:
			print('path: %s' % str(permute))
for i in range(1, 25000):
	generate(i)
process_input()


from math import sqrt, inf

class DownToZero:

	def __init__(self, limit):
		self.limit = limit
		self.size = limit + 1
		self.memo = [inf] * self.size
		self.memoization()

	def memoization(self):
		m = self.memo
		m[0] = 0
		m[1] = 1
		m[2] = 2
		for i in range(2, len(m)):
			m[i] = min(m[i], m[i - 1] + 1)
			for j in range(2 * i, min(i * i + 1, len(m)), i):
				m[j] = min(m[j], m[i] + 1)

	def calc(self, n):
		return self.memo[n]

def main():
	Q = int(input())
	Ns = list(map(int, input().split()))
	downer = DownToZero(max(Ns))
	for n in Ns:
		print(downer.calc(n))

def main2():
	Q = int(input())
	Ns = [int(input()) for _ in range(Q)]
	downer = DownToZero(max(Ns))
	for n in Ns:
		print(downer.calc(n))
main2()


import math
from collections import namedtuple
Node = namedtuple('Node', ['value', 'counter', 'parent'])
dict_divisors = {}
dict_path = {}

def get_divisors(n):
	if n in dict_divisors:
		return dict_divisors[n]
	divisors = set()
	if n <= 3:
		return divisors
	for i in range(int(math.sqrt(n)) + 1, 1, -1):
		if n % i == 0:
			divisors.add(max(i, int(n / i)))
	dict_divisors[n] = divisors
	return divisors

def find_path(n):
	if n in dict_path:
		return dict_path[n]
	queue = list()
	processed = {}
	add_node(Node(n, 0, None), queue, processed)
	counter = n
	while queue:
		node = queue.pop()
		if node.value == 0:
			counter = node.counter
			break
		for i in get_divisors(node.value):
			add_node(Node(i, node.counter + 1, node), queue, processed)
		add_node(Node(node.value - 1, node.counter + 1, node), queue, processed)
	dict_path[n] = counter
	return counter

def add_node(node, queue, processed):
	if node.value in processed:
		if processed[node.value] <= node.counter:
			return
	queue.insert(0, node)
	processed[node.value] = node.counter

def print_path(node):
	path = []
	current = node
	while current:
		path.append(current.value)
		current = current.parent
	print(*path, sep='->')
for _ in range(int(input().strip())):
	n = int(input().strip())
	counter = find_path(n)
	print(counter)


import sys
import math
Q = int(input().strip())
dp = [-1 for i in range(10 ** 6 + 1)]
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(10 ** 6 + 1):
	if dp[i] == -1 or dp[i] > dp[i - 1] + 1:
		dp[i] = dp[i - 1] + 1
	j = 1
	while j <= i and j * i <= 10 ** 6:
		if dp[i * j] == -1 or dp[i] + 1 < dp[i * j]:
			dp[i * j] = dp[i] + 1
		j += 1
for a0 in range(Q):
	print(dp[int(input())])


import sys
max_N = 1000000
data = [sys.maxsize] * (max_N + 1)
data[0] = 0
data[1] = 1
for a in range(1, max_N):
	val = data[a]
	data[a + 1] = min(data[a + 1], val + 1)
	for b in range(2, a + 1):
		p = a * b
		if p > max_N:
			break
		data[p] = min(data[p], val + 1)
Q = int(input())
for tid in range(Q):
	N = int(input())
	print(data[N])


import sys
nums = [0] * 1000001
nums[1] = 1
nums[2] = 2
nums[3] = 3
nums[4] = 3
for i in range(1, 1000000):
	newnum = nums[i] + 1
	for j in range(2, min(i + 1, 1000000 // i + 1)):
		if nums[i * j] == 0 or nums[i * j] > newnum:
			nums[i * j] = newnum
	if nums[i + 1] == 0 or nums[i + 1] > newnum:
		nums[i + 1] = newnum
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


from collections import deque
qlst = [int(input()) for _ in range(int(input()))]
LIM = max(qlst) + 1
min_ops = [None] * LIM
min_ops[0] = 0
min_ops[1] = 1
que = deque()
que.append(1)
for N in qlst:
	while min_ops[N] is None:
		n = que.popleft()
		for p in range(n + n, min(n * n + 1, LIM), n):
			if min_ops[p] is None:
				min_ops[p] = min_ops[n] + 1
				que.append(p)
		if n + 1 < LIM and min_ops[n + 1] is None:
			min_ops[n + 1] = min_ops[n] + 1
			que.append(n + 1)
	print(min_ops[N])


q = int(input())
N = 1000001
dp = [N] * N
dp[0] = 0
dp[1] = 1
for i in range(2, N):
	dp[i] = min(dp[i - 1] + 1, dp[i])
	for j in range(2, i + 1):
		if j * i >= N:
			break
		dp[j * i] = min(dp[i] + 1, dp[j * i])
for i in range(q):
	n = int(input())
	print(dp[n])


import sys
limit = 1000001
array = [limit] * limit
array[0:4] = [0, 1, 2, 3]
for i in range(1, limit):
	array[i] = min(array[i], array[i - 1] + 1)
	for j in range(i, min(i * i + 1, limit), i):
		array[j] = min(array[j], array[i] + 1)
Q = int(input().strip())
for a0 in range(Q):
	print(array[int(input().strip())])


import sys
from collections import deque
import math

def add_child(fringe, score, seen, child):
	if child not in seen:
		fringe.append((score, child))
		seen.add(child)
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	fringe = deque([(0, N)])
	seen = set()
	while len(fringe) > 0:
		(score, num) = fringe.popleft()
		if num == 0:
			print(score)
			break
		elif num == 1:
			add_child(fringe, score + 1, seen, 0)
			continue
		elif num == 2:
			add_child(fringe, score + 2, seen, 0)
			continue
		elif num == 3:
			add_child(fringe, score + 3, seen, 0)
			continue
		elif num == 4:
			add_child(fringe, score + 3, seen, 0)
			continue
		child1 = num - 1
		if child1 not in seen:
			fringe.append((score + 1, child1))
			seen.add(child1)
		for val in range(2, math.floor(math.sqrt(num)) + 1):
			if num % val == 0:
				child2 = num // val
				if child2 not in seen:
					fringe.append((score + 1, child2))
					seen.add(child2)


Q = int(input().strip())
Nlist = [int(input().strip()) for i in range(Q)]
Nmax = max(Nlist)
mlist = [i for i in range(Nmax + 1)]
for i in range(2, Nmax):
	mlist[i + 1] = min(mlist[i] + 1, mlist[i + 1])
	for j in range(2, min(i, Nmax // i) + 1):
		mlist[i * j] = min(mlist[i * j], mlist[i] + 1)
for N in Nlist:
	print(mlist[N])


import sys
import math
Q = int(input().strip())
maxSize = 1000000
solutions = [None] * (maxSize + 1)
solutions[0] = 0
solutions[1] = 1
solutions[2] = 2
solutions[3] = 3
for i in range(2, maxSize):
	if solutions[i] is None:
		solutions[i] = solutions[i - 1] + 1
	else:
		solutions[i] = min(solutions[i - 1] + 1, solutions[i])
	mult = 2
	while mult * i <= maxSize and mult <= i:
		if solutions[mult * i] is None or solutions[mult * i] > solutions[i] + 1:
			solutions[mult * i] = solutions[i] + 1
		mult += 1
for a0 in range(Q):
	N = int(input().strip())
	print(solutions[N])


import sys
ways = [10 ** 7] * (10 ** 6 + 2)
ways[0] = 0
ways[1] = 1
ways[2] = 2
for i in range(2, len(ways) - 1):
	ways[i + 1] = min(ways[i + 1], ways[i] + 1)
	for j in range(i + i, min(i * i + 1, len(ways)), i):
		ways[j] = min(ways[j], ways[i] + 1)
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(ways[N])


import sys
import math

def get_counts(max_n):
	arr = [1 for i in range(max_n + 1)]
	for i in range(2, math.ceil(math.sqrt(max_n))):
		j = i + i
		while j < max_n + 1:
			c = arr[j]
			c2 = j // c
			if max(i, j // i) < max(c, c2):
				arr[j] = i
			j += i
	return arr

def test():
	arr = get_counts(30)
	for i in range(1, len(arr)):
		print(i, arr[i])
max_n = 1000000

def solve(N, arr):
	c = N
	count = 0
	while c > 0:
		ab = arr[c]
		if ab == 1:
			c -= 1
		else:
			c = max(ab, c // ab)
		count += 1
	return count

def get_dp_counts(max_n):
	arr = [-1 for i in range(max_n + 1)]
	arr[0] = 0
	arr[1] = 1
	arr[2] = 2
	arr[3] = 3
	for i in range(1, max_n + 1):
		if arr[i] == -1 or arr[i] > arr[i - 1] + 1:
			arr[i] = arr[i - 1] + 1
		j = 1
		while j <= i and j * i <= max_n:
			if arr[j * i] == -1 or arr[j * i] > arr[i] + 1:
				arr[j * i] = arr[i] + 1
			j += 1
	return arr
dp_counts = get_dp_counts(max_n)
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(dp_counts[N])


import sys
from queue import deque
factors = {}
Q = int(input().strip())

def min_moves(N):

	def neighbors(N):
		if N in factors:
			return factors[N]
		ns = [N - 1]
		i = int(N ** 0.5)
		while i >= 2:
			if N % i == 0:
				ns.append(N // i)
			i = i - 1
		factors[N] = ns
		return ns
	fringe = deque()
	fringe.append(N)
	numTo = {}
	curr = None
	numTo[N] = 0
	while len(fringe) > 0:
		curr = fringe.popleft()
		if curr == 4:
			return numTo[curr] + 3
		elif curr < 4:
			return numTo[curr] + curr
		for n in neighbors(curr):
			fringe.append(n)
			if n not in numTo or numTo[curr] + 1 < numTo[n]:
				numTo[n] = numTo[curr] + 1
for a0 in range(Q):
	N = int(input().strip())
	print(min_moves(N))


import sys
f = {}

def elim(x):
	hist = {x}
	s1 = [(x, 0)]
	s2 = []
	while len(s1) + len(s2) > 0:
		if len(s2) == 0:
			while len(s1) > 0:
				s2.append(s1.pop())
		(c, moves) = s2.pop()
		if c == 0:
			return moves
		if c == 1:
			return moves + 1
		if c == 2:
			return moves + 2
		if c == 3 or c == 4:
			return moves + 3
		if c - 1 not in hist:
			hist.add(c - 1)
			s1.append((c - 1, moves + 1))
		if c in f:
			factors = f[c]
		else:
			factors = []
			for a in range(2, int(c ** 0.5) + 2):
				if c % a == 0 and a <= c // a:
					factors.append(a)
			f[c] = factors
		for factor in factors:
			if c // factor not in hist:
				hist.add(c // factor)
				s1.append((c // factor, moves + 1))
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(elim(N))


from queue import deque
import sys
Q = int(input().strip())
N = [int(input().strip()) for _ in range(Q)]
maxN = max(N) + 1
calQueue = deque((0,))
table = [0] * maxN
while calQueue:
	i = calQueue.popleft()
	steps = table[i] + 1
	if i + 1 < maxN and table[i + 1] == 0:
		table[i + 1] = steps
		calQueue.append(i + 1)
	offset = i
	for j in range(i - 1):
		offset += i
		if offset >= maxN:
			break
		elif table[offset] == 0:
			table[offset] = steps
			calQueue.append(offset)
for n in N:
	print(table[n])


import sys
N = 1000000
factors = [[] for _ in range(N + 1)]
for i in range(2, N + 1):
	if i * i > N:
		break
	for j in range(i, N + 1, i):
		if i * i <= j:
			factors[j].append(i)
minMoves = [float('inf') for _ in range(N + 1)]
minMoves[0] = 0
for i in range(1, N + 1):
	minMoves[i] = min(minMoves[i - 1] + 1, min([minMoves[i // x] + 1 for x in factors[i]], default=float('inf')))
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(minMoves[N])


import sys
maxn = 10 ** 6 + 1
dp = [-1] * maxn
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
for i in range(maxn):
	if dp[i] < 0 or dp[i] > dp[i - 1] + 1:
		dp[i] = dp[i - 1] + 1
	j = 1
	while j <= i and i * j < maxn:
		if dp[i * j] == -1 or dp[i] + 1 < dp[i * j]:
			dp[i * j] = dp[i] + 1
		j += 1
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(dp[N])


L = 1000000
cost = [-1] * (L + 1)
cost[0] = 0
cost[1] = 1
Q = [0] * (L + 1)
head = 0
tail = 1
Q[head] = 1
while head < tail:
	n = Q[head]
	if n + 1 <= L and cost[n + 1] == -1:
		cost[n + 1] = cost[n] + 1
		Q[tail] = n + 1
		tail += 1
	j = 2
	while j <= n and j * n <= L:
		if cost[j * n] == -1:
			cost[j * n] = cost[n] + 1
			Q[tail] = j * n
			tail += 1
		j += 1
	head += 1
for _ in range(int(input())):
	n = int(input())
	print(cost[n])


class Queue:

	def __init__(self):
		self._queue = []
		self._count = 0
		self._first_element = 0

	def enqueue(self, value):
		self._queue.append(value)
		self._count += 1

	def dequeue(self):
		if self._count > 0:
			self._first_element += 1
			self._count -= 1
		else:
			while True:
				pass
			raise Exception('Empty array')

	def peek(self):
		if self._count > 0:
			return self._queue[self._first_element]
		else:
			while True:
				pass
			raise Exception('Empty array')

	def empty(self):
		return self._count == 0

	def clean(self):
		self._queue = []
		self._count = 0
		self._first_element = 0
queue = Queue()
check_list = [0] * 10000011
check_list[1] = 1
check_list[2] = 2
check_list[3] = 3
repeated_numbers = [False] * 10000011
m = 2
queue.enqueue(m)
for k in range(2, 1000000):
	iteration = 2
	product = iteration * m
	while iteration <= m and product <= 1000000:
		if not repeated_numbers[product]:
			check_list[product] = check_list[m] + 1
			repeated_numbers[product] = True
			queue.enqueue(product)
		iteration += 1
		product = iteration * m
	if not repeated_numbers[m + 1]:
		repeated_numbers[m + 1] = True
		queue.enqueue(m + 1)
		check_list[m + 1] = check_list[m] + 1
	queue.dequeue()
	m = queue.peek()
for i in range(int(input())):
	n = int(input())
	print(check_list[n])


import sys
from math import floor
from queue import Queue
maxx = 1000002
a = [-1] * maxx
a[0] = 0
for i in range(0, maxx - 1):
	if a[i + 1] < 0 or a[i + 1] > a[i] + 1:
		a[i + 1] = a[i] + 1
	for j in range(2, i + 1):
		k = i * j
		if k >= maxx:
			break
		if a[k] < 0 or a[k] > a[i] + 1:
			a[k] = a[i] + 1
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(a[N])


import sys
maxN = 10 ** 6
steps = {0: 0}
numQueue = [0]
pQ = 0
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	while pQ < len(numQueue) and N not in steps:
		hQ = numQueue[pQ]
		pQ += 1
		if hQ + 1 not in steps:
			steps[hQ + 1] = steps[hQ] + 1
			numQueue.append(hQ + 1)
		if hQ > 1:
			for numi in range(2, hQ + 1):
				if numi * hQ > maxN:
					break
				if numi * hQ not in steps:
					steps[numi * hQ] = steps[hQ] + 1
					numQueue.append(numi * hQ)
	print(steps[N])


t = [0, 1] + [1000000] * 2000000
for i in range(1, 1000000):
	if t[i + 1] > t[i] + 1:
		t[i + 1] = t[i] + 1
	for j in range(2, min(1000001 // i + 1, i + 1)):
		if t[i * j] > t[i] + 1:
			t[i * j] = t[i] + 1
for _ in range(int(input())):
	print(t[int(input())])


def make_array():
	num = 10 ** 6 + 1
	ar = [0] * num
	ar[1] = 1
	ar[2] = 2
	ar[3] = 3
	for i in range(2, num // 2 + 1):
		if not ar[i]:
			ar[i] = ar[i - 1] + 1
		else:
			ar[i] = min(ar[i - 1] + 1, ar[i])
		j = 2 * i
		c = ar[i] + 1
		endLoop = i ** 2
		if endLoop > num:
			endLoop = num - 1
		while j <= endLoop:
			if not ar[j]:
				ar[j] = c
			elif c < ar[j]:
				ar[j] = c
			j += i
	for i in range(num // 2, num):
		if not ar[i]:
			ar[i] = ar[i - 1] + 1
		else:
			ar[i] = min(ar[i], ar[i - 1] + 1)
	return ar
ar = make_array()
for _ in range(int(input().strip())):
	i = int(input().strip())
	print(ar[i])


N_LIMIT = 1000001
steps = [N_LIMIT] * N_LIMIT
steps[0:1] = (0, 1)
for i in range(2, N_LIMIT):
	steps[i] = min(steps[i], steps[i - 1] + 1)
	j = 2
	while j <= i and j * i < N_LIMIT:
		steps[i * j] = min(steps[i * j], steps[i] + 1)
		j += 1
Q = int(input().strip())
for _ in range(Q):
	N = int(input().strip())
	print(steps[N])


import sys
maxN = 10 ** 6
vals = {i: None for i in range(maxN + 1)}
vals[0] = 0
for i in range(1, maxN + 1):
	if vals[i] is None:
		vals[i] = vals[i - 1] + 1
	else:
		vals[i] = min(vals[i], vals[i - 1] + 1)
	for j in range(2 * i, min(i * i, maxN) + 1, i):
		if vals[j] is None:
			vals[j] = vals[i] + 1
		else:
			vals[j] = min(vals[j], vals[i] + 1)
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(vals[N])


import sys

def build_answers():
	min_steps = [i for i in range(1000001)]
	for n in range(2, 1000001):
		min_steps[n] = min((min_steps[n - 1] + 1, min_steps[n]))
		for i in range(2, min((n, 1000000 // n)) + 1):
			min_steps[n * i] = min((min_steps[n] + 1, min_steps[n * i]))
	return min_steps
answers = build_answers()
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(answers[N])


import sys
dp = [i for i in range(10 ** 6 + 1)]
for i in range(2, 10 ** 6):
	dp[i + 1] = min(dp[i + 1], dp[i] + 1)
	for j in range(2, i + 1):
		if i * j > 10 ** 6:
			break
		dp[i * j] = min(dp[i * j], dp[i] + 1)
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(dp[N])


def f(N):
	i = 0
	Q = [(N, 0)]
	S = set()
	while Q:
		(n, d) = Q[i]
		i += 1
		if n == 0:
			return d
		for k in range(2, int(n ** 0.5) + 1):
			if n % k == 0:
				m = max(k, n // k)
				if m not in S:
					Q.append((m, d + 1))
					S.add(m)
		if n - 1 not in S:
			Q.append((n - 1, d + 1))
			S.add(n - 1)
Q = int(input())
for q in range(Q):
	N = int(input())
	print(f(N))


import sys
max_value = 1000001
nums = [-1] * max_value
nums[0] = 0
nums[1] = 1
nums[2] = 2
nums[3] = 3
for i in range(max_value):
	if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
		nums[i] = nums[i - 1] + 1
	j = 1
	while j <= i and j * i < max_value:
		if nums[j * i] == -1 or nums[i] + 1 < nums[j * i]:
			nums[j * i] = nums[i] + 1
		j += 1
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


import sys
import functools
max_ = 1000001
dp = list(range(max_))
for n in range(2, max_):
	dp[n] = min(dp[n - 1] + 1, dp[n])
	for i in range(2, min(n, (max_ - 1) // n) + 1):
		dp[n * i] = min(dp[n] + 1, dp[n * i])
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(dp[N])


import sys
MAX = 1000001
ans = [-1] * MAX
ans[0] = 0
ans[1] = 1
ans[2] = 2
ans[3] = 3
for i in range(MAX):
	if ans[i] == -1 or ans[i] > ans[i - 1] + 1:
		ans[i] = ans[i - 1] + 1
	j = 1
	while j <= i and j * i < MAX:
		if ans[i * j] == -1 or ans[i] + 1 < ans[i * j]:
			ans[i * j] = ans[i] + 1
		j += 1
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(ans[N])


import sys
max_num = 10 ** 6
nums = [-1] * max_num
nums[0] = 0
nums[1] = 1
nums[2] = 2
nums[3] = 3
for i in range(2, max_num):
	if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
		nums[i] = nums[i - 1] + 1
	j = 2
	while j * i < max_num and j <= i:
		if nums[j * i] == -1 or nums[j * i] > nums[i] + 1:
			nums[j * i] = nums[i] + 1
		j += 1
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


import sys

def precompute():
	N = 1000001
	moves = [-1] * (N + 1)
	moves[0] = 0
	moves[1] = 1
	moves[2] = 2
	moves[3] = 3
	for i in range(1, N + 1):
		if moves[i] == -1 or moves[i] > moves[i - 1] + 1:
			moves[i] = moves[i - 1] + 1
		j = 2
		while j <= i and j * i <= N:
			if moves[i * j] == -1 or moves[i] + 1 < moves[i * j]:
				moves[i * j] = moves[i] + 1
			j += 1
	return moves
moves = precompute()
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(moves[N])


import sys
import math

def findMinOps(dp):
	for i in range(2, len(dp)):
		if dp[i] == -1 or dp[i] > dp[i - 1] + 1:
			dp[i] = dp[i - 1] + 1
		for j in range(2, i + 1):
			if i * j >= len(dp):
				break
			if dp[i * j] == -1:
				dp[i * j] = dp[i] + 1
			else:
				dp[i * j] = min(dp[i * j], dp[i] + 1)
Q = int(input().strip())
queries = []
for _ in range(Q):
	queries.append(int(input().strip()))
dp = [-1] * max(max(queries) + 1, 2)
(dp[0], dp[1]) = (0, 1)
findMinOps(dp)
for N in queries:
	print(dp[N])


import sys

def minMoves():
	m = 10 ** 6 + 1
	nums = [-1] * m
	for i in range(4):
		nums[i] = i
	for i in range(m):
		if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
			nums[i] = nums[i - 1] + 1
		j = 2
		while j <= i and j * i < m:
			if nums[i * j] == -1 or nums[i * j] > nums[i] + 1:
				nums[i * j] = nums[i] + 1
			j += 1
	return nums
nums = minMoves()
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


import sys
nums = []
maxL = 1000001
for i in range(maxL):
	nums.append(-1)
for x in range(4):
	nums[x] = x
for i in range(0, maxL):
	if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
		nums[i] = nums[i - 1] + 1
	for j in range(1, i + 1):
		if j <= i and j * i < maxL:
			if nums[j * i] == -1 or nums[i] + 1 < nums[j * i]:
				nums[j * i] = nums[i] + 1
		else:
			break
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


import sys

def minMoves():
	m = 10 ** 6 + 1
	nums = [-1] * m
	for i in range(4):
		nums[i] = i
	for i in range(m):
		if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
			nums[i] = nums[i - 1] + 1
		j = 2
		while j <= i and j * i < m:
			if nums[i * j] == -1 or nums[i * j] > nums[i] + 1:
				nums[i * j] = nums[i] + 1
			j += 1
	return nums
nums = minMoves()
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


import sys

def stepsArray():
	maxNumber = 10 ** 6
	tab = [-1] * maxNumber
	for i in range(maxNumber):
		if tab[i] == -1 or tab[i] > tab[i - 1] + 1:
			tab[i] = tab[i - 1] + 1
		j = 2
		while j <= i and j * i < maxNumber:
			if tab[i * j] == -1 or tab[i * j] > tab[i] + 1:
				tab[i * j] = tab[i] + 1
			j += 1
	return tab
tab = stepsArray()
Q = int(input())
for a0 in range(Q):
	print(tab[int(input())])


import sys

def minMoves():
	m = 10 ** 6 + 1
	nums = [-1] * m
	for i in range(4):
		nums[i] = i
	for i in range(m):
		if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
			nums[i] = nums[i - 1] + 1
		j = 2
		while j <= i and j * i < m:
			if nums[i * j] == -1 or nums[i * j] > nums[i] + 1:
				nums[i * j] = nums[i] + 1
			j += 1
	return nums
nums = minMoves()
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(nums[N])


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	n = int(input())
	print(moves[n])


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import math

def Sol(N):
	if N == 0:
		return 0
	Q = [(N, 0)]
	setQ = [0] * N
	while Q:
		(N, steps) = Q.pop(0)
		if N == 1:
			return steps + 1
		div = int(math.sqrt(N))
		while div > 1:
			if N % div == 0 and (not setQ[N // div]):
				Q.append((N // div, steps + 1))
				setQ[N // div] = 1
			div -= 1
		if not setQ[N - 1]:
			Q.append((N - 1, steps + 1))
			setQ[N - 1] = 1
Q = int(input())
for _ in range(Q):
	N = int(input())
	print(Sol(N))


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import sys
from math import sqrt, floor

def steps(N):
	values = [0] * (N + 1)
	values[1] = 1
	values[2] = 2
	values[3] = 3
	for index in range(2, N + 1):
		if values[index] == 0 or values[index] > values[index - 1] + 1:
			values[index] = values[index - 1] + 1
		for second in range(1, index + 1):
			if second * index > N:
				break
			if values[second * index] == 0 or values[second * index] > values[index] + 1:
				values[second * index] = values[index] + 1
	return values
Q = int(input().strip())
count = steps(1000001)
for a0 in range(Q):
	N = int(input().strip())
	print(count[N])


import sys

def generate_seive():
	limit = pow(10, 6) + 1
	seive = [-1] * limit
	(seive[0], seive[1], seive[2], seive[3]) = (0, 1, 2, 3)
	for iind in range(limit):
		if seive[iind] == -1 or seive[iind] > seive[iind - 1] + 1:
			seive[iind] = seive[iind - 1] + 1
		jind = 1
		while jind <= iind and jind * iind < limit:
			if seive[jind * iind] == -1 or seive[jind * iind] > seive[iind] + 1:
				seive[jind * iind] = seive[iind] + 1
			jind += 1
	return seive
Q = int(input().strip())
seive = generate_seive()
for a0 in range(Q):
	N = int(input().strip())
	print(seive[N])


import sys

def fillTable(N):
	lookup = [None] * (N + 1)
	lookup[0] = 0
	for i in range(1, N + 1):
		if lookup[i] is None or lookup[i] > lookup[i - 1] + 1:
			lookup[i] = lookup[i - 1] + 1
		for j in range(2, i + 1):
			prod = i * j
			if prod > N:
				break
			if lookup[prod] is None or lookup[prod] > lookup[i] + 1:
				lookup[prod] = lookup[i] + 1
	return lookup
Q = int(input().strip())
queries = []
for a0 in range(Q):
	N = int(input().strip())
	queries.append(N)
lookup = fillTable(max(queries))
for N in queries:
	print(lookup[N])


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import sys
Q = int(input().strip())
m = 1000001
arr = [None] * m
arr[0] = 0
arr[1] = 1
for i in range(1, m):
	if arr[i] == None or arr[i] > arr[i - 1] + 1:
		arr[i] = arr[i - 1] + 1
	j = 2
	while j <= i and i * j < m:
		if arr[i * j] == None or arr[i * j] > arr[i] + 1:
			arr[i * j] = arr[i] + 1
		j += 1
for a0 in range(Q):
	N = int(input().strip())
	print(arr[N])


import sys
Q = int(input().strip())
Ns = []
for a0 in range(Q):
	N = int(input().strip())
	Ns.append(N)
MaxN = max(Ns)
dividers = list(([] for i in range(MaxN + 1)))
for i in range(2, int(MaxN ** 0.5) + 1):
	p = i * i
	j = i
	while p <= MaxN:
		dividers[p].append(j)
		j += 1
		p += i

def solve(N):
	if N < 4:
		return N
	step = 0
	tested = set()
	curr_set = set([N])
	while True:
		step += 1
		next_set = set()
		for p in curr_set:
			for j in dividers[p]:
				if j < 3:
					return step + j
				if not j in tested:
					tested.add(j)
					next_set.add(j)
			j = p - 1
			if j < 4:
				return step + j
			if not j in tested:
				tested.add(j)
				next_set.add(j)
		curr_set = next_set
for N in Ns:
	print(solve(N))


import sys
N = 1000000
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import sys
min_steps = [x for x in range(1000001)]
for n in range(2, 1000001):
	min_steps[n] = min((min_steps[n - 1] + 1, min_steps[n]))
	for i in range(2, min((n, int(1000000 / n))) + 1):
		min_steps[n * i] = min((min_steps[n] + 1, min_steps[n * i]))
Q = int(input().strip())
for a0 in range(Q):
	N = int(input().strip())
	print(min_steps[N])


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import math

class Solution:

	def __init__(self):
		self.table = [-1 for x in range(1000001)]
		self.table[1] = 1
		self.table[2] = 2
		self.table[3] = 3
		self.table[4] = 3
		self.table[0] = 0
		for i in range(1, 1000001):
			if self.table[i] == -1 or self.table[i] > self.table[i - 1] + 1:
				self.table[i] = self.table[i - 1] + 1
			j = 2
			while j <= i and j * i < 1000001:
				if self.table[i * j] == -1 or self.table[i] + 1 < self.table[i * j]:
					self.table[j * i] = self.table[i] + 1
				j += 1

	def resolve(self, n):
		return self.table[n]
Q = int(input().strip())
s = Solution()
for a0 in range(Q):
	N = int(input().strip())
	print(s.resolve(N))


def populate(n):
	nums = [0, 1, 2, 3, 3] + [-1] * (n - 4)
	for i in range(n + 1):
		if nums[i] == -1 or nums[i] > nums[i - 1] + 1:
			nums[i] = nums[i - 1] + 1
		for j in range(1, i + 1):
			if i * j > n:
				break
			if nums[i * j] == -1 or nums[i] + 1 < nums[i * j]:
				nums[j * i] = nums[i] + 1
	return nums
Q = int(input().strip())
N = [int(input().strip()) for _ in range(Q)]
max_ = max(N)
p = populate(max_)
for i in N:
	print(p[i])


N = 10 ** 6
moves = [0] + N * [N]
for i in range(N):
	moves[i + 1] = min(moves[i + 1], moves[i] + 1)
	j = 2
	while j <= i and j * i <= N:
		moves[i * j] = min(moves[i * j], moves[i] + 1)
		j += 1
for _ in range(int(input())):
	print(moves[int(input())])


import sys
max_num = 10 ** 6
dp = [0] + max_num * [float('inf')]
for i in range(max_num):
	dp[i + 1] = min(dp[i + 1], dp[i] + 1)
	j = 2
	while j <= i and j * i <= max_num:
		dp[i * j] = min(dp[i * j], dp[i] + 1)
		j += 1
n = int(input().strip())
for _ in range(n):
	num = int(input().strip())
	print(dp[num])


import sys
import math

def minMove(n):
	res = [1000000.0] * (n + 1)
	res[0] = 0
	if n >= 1:
		res[1] = 1
		pos = 2
		while pos <= n:
			res[pos] = min(res[pos], res[pos - 1] + 1)
			i = 2
			while i <= pos and i * pos <= n:
				res[i * pos] = min(res[i * pos], res[pos] + 1)
				i += 1
			pos += 1
	return res
Q = int(input().strip())
Nvals = []
for a0 in range(Q):
	N = int(input().strip())
	Nvals.append(N)
res = minMove(max(Nvals))
for a0 in range(Q):
	print(res[Nvals[a0]])