Limits 1s, 512 MB

Leonhard’s math teacher loves prime numbers. As homework, the teacher gave Leonhard a number nn, told him to do extensive research and find out whether the number was prime or not. Here, nn is a natural number with no more than 1212 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(1T105)T(1 ≤ T ≤ 10^5), denoting the number of test cases. The next TT lines will contain the reconstructed number nn for that test case. As mentioned earlier, nn is a natural number with no more than 1212 digits and no leading zeroes.

Output

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

Sample

InputOutput
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.

Submit

Login to submit.

Statistics

43% Solution Ratio
s_semicolonEarliest, Dec '21
NirjhorFastest, 0.2s
NirjhorLightest, 1.1 MB
NirjhorShortest, 1613B
Toph uses cookies. By continuing you agree to our Cookie Policy.