#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'downToZero' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER n as parameter.
#


# Python program to print all Primes Smaller 
# than or equal to N using Sieve of Eratosthenes
  
  
def SieveOfEratosthenes(num):
    prime = [True for i in range(num+1)]
    arr = []
    p = 2
    while (p * p <= num):
        if (prime[p] == True):
            for i in range(p * p, num+1, p):
                prime[i] = False
        p += 1
    for p in range(2, num+1):
        if prime[p]:
            arr.append(p)
    return arr
arr = SieveOfEratosthenes(1000000)
arr = set(arr)
# print(arr)
def check(n):
    if n in arr:
        return 0
    for i in range(int(math.sqrt(n))+1, 2, -1):
        if n % i == 0:
            return n//i
    return 0

def downToZero(n):
    dp = [-1 for i in range(n+1)]
    def solve(val):
        if val == 1:
            return 1
        if dp[val] != -1:
            return dp[val]
        vv = check(val)
        aa = float("inf")
        if vv:
            aa = 1 + solve(vv)
        dp[val] = min(aa, 1 + solve(val-1))
        return dp[val]
    return solve(n)
            
        
        
        
        
        
        
        
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input().strip())

    for q_itr in range(q):
        n = int(input().strip())

        result = downToZero(n)

        fptr.write(str(result) + '\n')

    fptr.close()