You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定 $n$ 个数 $a_i$，请你判断 $\prod_{i = 1}^n a_i$ 是否为质数。

提示：$\prod_{i = 1}^n a_i = a_1 \times a_2 \times \dots \times a_n$。

Format

Input

• 第 $1$ 行：$1$ 个整数 $n$；
• 第 $2$ 行：$n$ 个整数 $a_i$。

Output

若 $\prod_{i = 1}^n a_i$ 为质数，输出 Prime!，否则输出 Not prime!。

Samples

2
1 2

Prime!

$1 \times 2 = 2$，$2$ 为质数。

3
1 2 3

Not prime!

$1 \times 2 \times 3 = 6$，$6$ 不为质数。

Limitation

本题采用捆绑测试。

• 对于 $10\%$ 的数据，$\prod a_i \le 10^9$。
• 对于另外 $10\%$ 的数据，$n = 1$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。