Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Dog Ate My Homework

By curly_braces · 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.

Discussion

Statistics


56% Solution Ratio

s_semicolonEarliest, 1M ago

NirjhorFastest, 0.2s

NirjhorLightest, 1.1 MB

NirjhorShortest, 1613B

Submit

Login to submit

Editorial

Using divisibility rules, It can be proven that if you take a prime number and replace two or more o...

Toph uses cookies. By continuing you agree to our Cookie Policy.