We have N integers. The i-th number is A_i.

\\{A_i\\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\\{A_i\\} is said to be setwise coprime when \\{A_i\\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \\{A_i\\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

* 2 \leq N \leq 10^6
* 1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:


N
A_1 \ldots A_N


Output

If \\{A_i\\} is pairwise coprime, print `pairwise coprime`; if \\{A_i\\} is setwise coprime, print `setwise coprime`; if neither, print `not coprime`.

Examples

Input

3
3 4 5


Output

pairwise coprime


Input

3
6 10 15


Output

setwise coprime


Input

3
6 10 16


Output

not coprime
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1e6 + 10;
int n, pr[MAXN], a[MAXN];
void div(int x)
{
	for (int i = 2; i*i <= x; i++)
	{
		if (x%i == 0)
		{
			pr[i] += 1;
			while (x%i == 0)
				x /= i;
		}
	}
	if (x > 1)
		pr[x] += 1;
}
int main()
{
//	freopen("in.txt", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		div(a[i]);
	}
	int flag = 0;
	for (int i = 1; i <= 1e6; i++)
	{
		if (pr[i] > 1)
			flag = 1;
		if (pr[i] == n)
		{
			flag = 2;
			break;
		}
	}
	if (flag == 0)
		printf("pairwise coprime\n");
	else if (flag == 1)
		printf("setwise coprime\n");
	else
		printf("not coprime\n");
	return 0;
}
