A prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself. The task is to test whether a number is a prime number.

Without taking into consideration efficiency aspects we can focus on solution arising directly from the problem definition. At first we present the imperative approach expressed in C language:

#include<stdio.h>

int isPrime(int n)
{
  int i, divisors = 0;
  for (i = 1; i <= n; i++) {
    if (n % i == 0) divisors++;
  }
  return divisors == 2;
}

int main()
{
  int n;
  while(scanf("%d\n", &n) != -1) {
    printf("%d\n", isPrime(n));
  }
  return 0;
}

The problem solution is encapsulated in the isPrime function, where we prepare variable divisors which is intended to contain the number of divisors of number n. We need to loop over all possible divisors (i.e. from 1 to n) and for each one we verify if it is a divisor. The number n is a prime number if and only if the number of its divisors equals exactly two. It's simple and almost direct but it still requires a bit of analysing. 

Let us now consider a functional way of thinking about the solution. We don't have any loops or changing state in functional programming thus there is no natural equivalent of presented C solution. Definition of the prime number states: "a prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself". In functional languages it is natural to operate on lists - to solve the prime problem directly from the definition we should take a list of all possible divisors of n, filter it to keep only real divisors and compare it with [1,n] list. If these lists are identical the number n is a prime number. Look at the Haskell code:

type Input = Int
type Output = Bool

-- Input / Output

main :: IO ()
main = do
  ls <- fmap lines getContents
  mapM_ putStrLn $ map (showOutput . solution . readInput) ls

readInput :: String -> Input
readInput = read

showOutput :: Output -> String
showOutput b = if b == True then "1" else "0"

solution :: Input -> Output
solution = isPrime

-- Solution

isPrime :: Int -> Bool
isPrime n = [k | k <- [1..n], n `mod` k == 0] == [1,n]

The function isPrime is in fact the problem definition written in Haskell syntax.

The presented solutions are not even remotely efficient but they are correct and sufficient to positively accept this problem.

Input

The input contains a certain number of natural numbers n_i separated by newline. Each number is a single test case.

Output

In the i^th line print 1 if n_i is a prime number or print 0 otherwise.

Example

Input:
1
2
3
4
5
6
7

Output:
0
1
1
0
1
0
1