Hexadecimal String Prime Check

You are given a hexadecimal string which represents a number. The string consists of digits (0-9) and lowercase letters (a-f). Your task is to convert this hexadecimal string to its corresponding decimal integer value and check if it is a prime number.

If the number is prime, output Prime; otherwise, output Not Prime.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

The conversion of the hexadecimal to an integer should be done using base 16. Formally, if \( s \) is the given hexadecimal string then the integer value is \( N = \sum_{i=0}^{k-1} d_i \times 16^{(k-1-i)} \) where \( d_i \) is the digit value.

inputFormat

The input consists of a single line containing a non-empty hexadecimal string.

Example: 11

outputFormat

Output a single line containing either Prime if the converted number is prime, or Not Prime otherwise.

11

Prime