Leonhard’s math teacher loves prime numbers. As homework, the teacher gave Leonhard a number $n$, told him to do extensive research and find out whether the number was prime or not. Here, $n$ is a natural number with no more than $12$ digits and no leading zeroes. Returning home from school, Leonhard left the homework at his reading table and went out to play with his friends. After coming back, he found out that his worst nightmare has become a reality. You guessed it right, his dog tore the homework into pieces.

After collecting the bits and pieces, Leonhard tried to reconstruct the number; but some parts were missing. Probably the dog ate those parts. If any of the digits were missing, it might be impossible to find out whether the number was prime or not. As Leonhard’s teacher will not believe that his dog ate the homework, he came up with a strategy. If the probability that the number was not prime is more than the probability of it being prime (after filling the missing digits randomly), he will answer “Not Prime”, otherwise he will answer “Prime”.

You are given the reconstructed number where missing digits are represented as ‘x’. For example, if the number was “127” and the 2nd digit was missing, the reconstructed number will be “1x7”. Can you tell what Leonhard’s answer was?

Input

The first line of the input will contain a single integer $T(1 ≤ T ≤ 10^5)$, denoting the number of test cases. The next $T$ lines will contain the reconstructed number $n$ for that test case. As mentioned earlier, $n$ is a natural number with no more than $12$ digits and no leading zeroes.

Output

For each test case, print Leonhard’s answer in a new line.

Sample

Input

Output

4
7
2x
x3
3xx5

Prime
Not Prime
Prime
Not Prime

A natural number (1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it is greater than 1 and cannot be written as the product of two smaller natural numbers.