Problem Description

Takahashi loves prime number checking algorithms. He plays with various prime number checking algorithms every day. However, Takahashi has become tired of checking prime numbers because he has done it too much. Therefore, Takahashi decided to check if a number looks like a prime.

An integer \( N \) greater than or equal to \( 1 \) is judged to be "prime-like" or not as follows:

• If \( N \) is a prime number, then \( N \) is "prime-like".
• If \( N \) is a composite number, then \( N \) is "prime-like" if the last digit when \( N \) is written in base 10 is neither even nor 5, and the sum of its digits is not divisible by 3.
• In all other cases, \( N \) is not "prime-like".

Given an integer \( N \), output "Prime" if \( N \) is "prime-like", otherwise output "Not Prime".

Input Format

The input is given from the standard input in the following format:

\( N \)

• The first line contains an integer \( N \) \( (1 \leq N \leq 10^9) \).

Output Format

Output "Prime" if \( N \) is "prime-like", otherwise output "Not Prime".

End the output with a newline.

Sample Input and Output

Sample Input #1

42

Sample Output #1

Not Prime

Sample Input #2

49

Sample Output #2

Prime

Sample Input #3

3

Sample Output #3

Prime

Sample Input #4

1

Sample Output #4

Not Prime

Notes/Hints

Sample Explanation 1

\( 42 \) is a composite number and its last digit is even, so it is judged to be "not prime-like".

Sample Explanation 2

\( 49 \) is not a prime number, but it is judged to be "prime-like".

Sample Explanation 3

\( 3 \) is a prime number, so it is judged to be "prime-like".

Sample Explanation 4

\( 1 \) is neither a prime number nor a composite number, so it is judged to be "not prime-like".

见题面 Input 部分

见题面 Output 部分