問題文

高橋君は素数判定アルゴリズムが大好きです。毎日さまざまな素数判定アルゴリズムを実装して遊んでいます。 しかし、高橋君は素数判定をしすぎてしまったので、素数判定に飽きてしまいました。 そこで高橋君は、「素数っぽく見える数」判定をすることにしました。

1以上の整数Nは、以下のように「素数っぽい」かどうかが判定されます。

• Nが素数であるなら、Nは「素数っぽい」
• Nが合成数であるなら、Nを10進表記した時の1の位が偶数でも5でもなく、各桁の和が3で割り切れないならば、Nは「素数っぽい」
• それ以外の場合、Nは「素数っぽくない」

整数Nが与えられるので、Nが「素数っぽい」場合は"Prime"、そうでない場合は"Not Prime"と出力してください。

入力例1

42

出力例1

Not Prime

42は合成数かつ1の位が偶数なので、「素数っぽくない」と判定されます。

入力例2

49

出力例2

Prime

49は素数ではありませんが、「素数っぽい」と判定されます。

入力例3

3

出力例3

Prime

3は素数なので、「素数っぽい」と判定されます。

入力例4

1

出力例4

Not Prime

1は素数でも合成数でもないので、「素数っぽくない」と判定されます。