互质判断

题目描述

有 $N$ 个整数。第 $i$ 个数是 $A_i$。

当「对所有 $1\leq i \lt j \leq N$,有 $GCD(A_i,A_j)=1$」成立时,称 $\{A_i\}$ 是 pairwise coprime。

当 $\{A_i\}$ 不是 pairwise coprime,并且 $GCD(A_1,\ldots,A_N)=1$ 时,称 $\{A_i\}$ 是 setwise coprime。

请判断 $\{A_i\}$ 是 pairwise coprime、setwise coprime,还是两者都不是。

其中 $GCD(\ldots)$ 表示最大公约数。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $\ldots$ $A_N$

输出格式

如果 $\{A_i\}$ 是 pairwise coprime 输出 pairwise coprime,是 setwise coprime 输出 setwise coprime,两者都不是则输出 not coprime。

样例

3
3 4 5

pairwise coprime

因为 $GCD(3,4)=GCD(3,5)=GCD(4,5)=1$,所以是 pairwise coprime。

3
6 10 15

setwise coprime

因为 $GCD(6,10)=2$,所以不是 pairwise coprime;但 $GCD(6,10,15)=1$,所以是 setwise coprime。

3
6 10 16

not coprime

因为 $GCD(6,10,16)=2$,所以既不是 pairwise coprime 也不是 setwise coprime。

数据范围

• $2 \leq N \leq 10^6$
• $1 \leq A_i\leq 10^6$