Help Golu | Practice Problems

Help Golu

★★★★★

3.9

25 votes

Details

Problem

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

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

for N=2 one prime number (2)

for N=4 two prime numbers (2 + 2)