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<bits/stdc++.h>
using namespace std;
int read(){
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
const int N = 2e6+100;
int c[N],g[N],f[N],a[N],n;
int gcd(int a,int b){
	if(b==0) return a;return gcd(b,a%b);
}
int main()
{
	n = read();
	for(int i = 1;i <= n;i++){
		a[i] = read();c[a[i]]++;
		g[i] = gcd(a[i],g[i-1]);
	}
	if(g[n] != 1){
		cout <<"not coprime"<<endl;
		return 0;
	}
	for(int i = 2;i <= 1e6;i++){
		int sum = 0;
		for(int j = i;j <= 1e6;j+=i) sum+=c[j];
		if(sum>=2) { cout<<"setwise coprime"<<endl; return 0; }
	}
	cout<<"pairwise coprime"<<endl;
	return 0;
}