AT_arc044_a.[ARC044A] 素数判定

高桥君非常喜欢素数判定算法。他每天都会实现各种各样的素数判定算法来玩耍。然而，由于他判定素数太多，已经感到厌倦了。因此，高桥君决定进行“看起来像素数的数”的判定。

对于大于等于 $1$ 的整数 $N$，按照以下规则判断其是否“看起来像素数”：

• 如果 $N$ 是素数，则 $N$ 被认为是“看起来像素数”。
• 如果 $N$ 是合成数，并且 $N$ 的十进制表示的个位数字既不是偶数也不是 $5$，且各位数字之和不能被 $3$ 整除，则 $N$ 被认为是“看起来像素数”。
• 其他情况下，$N$ 被认为“不像素数”。

给定整数 $N$，如果 $N$ 是“看起来像素数”，输出 "Prime"；否则输出 "Not Prime"。

输入以以下格式从标准输入读入。

$N$

• 第 $1$ 行包含一个整数 $N$，满足 $1 \leq N \leq 10^9$。

如果 $N$ 是“看起来像素数”，输出 "Prime"；否则输出 "Not Prime"。

输出末尾需要换行符。

样例解释 1

$42$ 是合成数，且个位数字是偶数，因此被判定为“不像素数”。

样例解释 2

$49$ 虽然不是素数，但被判定为“看起来像素数”。

样例解释 3

$3$ 是素数，因此被判定为“看起来像素数”。

样例解释 4

$1$ 既不是素数也不是合成数，因此被判定为“不像素数”。

由 ChatGPT 4.1 翻译