Golu loves prime numbers . He wants to do something new with prime numbers. So Molu gives him a number and asks him to minmum number of prime numbers required such that their sum is equal to given number. This task is very diffcult for Golu so he asks you for your help.

Now your task is that you are given a number and you have to find minimum number of prime numbers required such that their sum is equal to given number.

INPUT  First line contains number of test cases T . Each test case contains a single integer N.
OUTPUT  For each test case print in a single line minmum number of primes numbers required. 
Constraints
1 ≤ T ≤ 1000000

2 ≤ N ≤ 1000000 

SAMPLE INPUT
2
2
4

SAMPLE OUTPUT
1
2

Explanation

for N=2 one prime number    (2)

for N=4  two prime numbers (2 + 2)
import math
def check(n):
	return all( n%i  for i in range(2, int(math.sqrt(n) )  + 1 ))
for i in range(input()):
	val = input() 
	print "1" if check(val) else "2" if check(val-2) or val % 2 == 0 else "3"









"""
import math
primes = []
def primeSieve(sieveSize):
	sieve = [True] * sieveSize
	sieve[0] = False 
	sieve[1] = False
	for i in range(2, int(math.sqrt(sieveSize)) + 1):
		pointer = i * 2
		while pointer < sieveSize:
			sieve[pointer] = False
			pointer += i
	for i in range(sieveSize):
		if sieve[i] == True:
			primes.append(i)
primeSieve(1000000)


for i in range(input()):
	val = input()
	if val == 1 :
		print "1"
	else :
		if val >2 and val%2 == 0:
			print "2"
		else:
			if val in primes:
				print "1"
			elif (val-2) in primes:
				print "2"
			else:
				print "3"
			
			
			"""