help-golu
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

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
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(eval(input())):
	val = eval(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")


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(eval(input())):
	val = eval(input())
	if val == 1 :
		print("1")
	else :
		if val >2 and val%2 == 0:
			print("2")
		else:
			if val in primes:
				print("1")
			else:
				if (val-2) in primes:
					print("2")
				else:
					print("3")


import math
def prime(a):
	n=int(math.sqrt(a))
	for x in range(2,n+1):
		if a%x==0:
			return 0
	return 1
t=eval(input())
while t:
	t-=1
	num=eval(input())
	if prime(num):
		print(1)
	elif num>2 and num%2==0:
		print(2)
	else:
		if prime(num-2):
			print(2)
		else:
			print(3)


def prime(a):
	return all(a % i for i in range(2, a))
for _ in range(eval(input())):
	n=eval(input())
	print("1" if prime(n) else "2" if prime(n-2) or n%2==0 else "3")


from math import sqrt
def prime(n):
	t=0
	for x in range(2,n):
		if n%x==0:
			t=1
			break
	if t==0:
		return True
	else :
		return False
for _ in range(eval(input())):
	n=eval(input())
	if prime(n):
		print("1")
	elif n%2==0 or prime(n-2):
		print("2")
	else :
		print("3")


def fun(n):
	if n==0:return 0
	elif prime(n):return 1
	else:
		x=find(n)
		n-=x
		return (1+fun(n))
def find(x):
	if prime(x):return x
	else:return(find(x-1))
def prime(x):
	i=2
	while i*i<=x:
		if x%i==0:return False
		i+=1
	return True

for _ in range(eval(input())):
	n=eval(input())
	if prime(n):print(1)
	elif n&1==0:print(2)
	elif prime(n-2):print(2)
	else:print(3)
	#print fun(n)


from math import sqrt
def prime(n):
	t=0
	for x in range(2,n):
		if n%x==0:
			t=1
			break
	return True if t==0 else False
for _ in range(eval(input())):
	n=eval(input())
	print("1" if prime(n) else "2" if prime(n-2) or n%2==0 else "3")