In HackerLand, they have a very strange monetary system.
Each gold coin has an integer number 'N' written on it.
A coin N can be split into any number of coins.
For example {11} can be split into {5,6} or {2,4,5} or any other possible way.

You are offered such a coin to take home. But your family does not like coins which have a prime number on it. Your task is to take home as few coins as possible without a prime number on it.

Input:

The first line of the input contains a single integer T denoting the number of test cases to follow. Each test case is a single line with a number N. It is the number written on your coin. Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100,000  

Output:

For each test case output a single line, containing the minimum number of coins.

SAMPLE INPUT
4
11
12345
12421
2444

SAMPLE OUTPUT
2
1
2
1

Explanation

Test case 1:
{11} -> {1,10}. So, you can take home a possible minimum of 2 coins. NOTE: 1 is non-prime.

Test case 2:
{12345} can be taken home without splitting.
Similar for the rest of the test cases.
def generate_primes(n):
  is_prime = [True] * (n + 1)
  for x in range(2, n + 1):
    i = 2
    while i * x < n + 1:
      is_prime[i * x] = False
      i += 1
  
  primes = {}
  for i in range(2, n + 1):
    if is_prime[i]:
      primes[i] = True

  return primes


def n_coins(n, primes):
  if n not in primes: return 1
  elif n == 3       : return 3  
  else              : return 2

def main():
  primes = generate_primes(100000)
  t = input()
  while t > 0:
    n = input()
    print n_coins(n, primes) 
    t -= 1
  

if __name__ == '__main__':
  main()