Subtract or Divide
Ridbit starts with an integer $$$n$$$.In one move, he can perform one of the following operations:   divide $$$n$$$ by one of its proper divisors, or  subtract $$$1$$$ from $$$n$$$ if $$$n$$$ is greater than $$$1$$$. A proper divisor is a divisor of a number, excluding itself. For example, $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, and $$$10$$$ are proper divisors of $$$20$$$, but $$$20$$$ itself is not.What is the minimum number of moves Ridbit is required to make to reduce $$$n$$$ to $$$1$$$?
For the test cases in the example, $$$n$$$ may be reduced to $$$1$$$ using the following operations in sequence$$$1$$$$$$2 \xrightarrow{} 1$$$$$$3 \xrightarrow{} 2 \xrightarrow{} 1$$$$$$4 \xrightarrow{} 2 \xrightarrow{} 1$$$$$$6 \xrightarrow{} 2 \xrightarrow{} 1$$$$$$9 \xrightarrow{} 3 \xrightarrow{} 2\xrightarrow{} 1$$$
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$).
For each test case, output the minimum number of moves required to reduce $$$n$$$ to $$$1$$$.
t = int(input())
a = []
for i in range(t):
    f = int(input())
    a.append(f)
for j in a:
    count = 0
    while j != 1:
        count += 1
        if j % 2 != 0:
            j -= 1
            count += 1
        z = j
        for c in range(j // 2, 1, -1):
            if j % c == 0:
                j //= c
                break
        if z == j:
            j -= 1
    print(count)
for i in range(0, int(input())):
    n = int(input())
    if n <= 3:
        print(n - 1)
    elif n % 2 == 0:
        print('2')
    else:
        print('3')
def test():
    n = int(input())
    c = 0
    if n > 3:
        if n % 2 == 1:
            print(3)
        else:
            print(2)
    else:
        print([0, 1, 2][n - 1])
t = int(input())
for _ in range(t):
    test()