Prime Number Checker

Given an integer $$M$$, determine whether it is a prime number. A prime number is defined as a number greater than 1 that has no positive divisors other than 1 and itself. The check can be optimized by testing divisibility up to $$\sqrt{M}$$. If the number is prime, output Prime; otherwise, output Not Prime.

inputFormat

Input is provided via standard input (stdin) as a single integer $$M$$.

outputFormat

Output via standard output (stdout) should be a single line containing either Prime or Not Prime.## sample

2

Prime