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
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] A = new int[N];
		for(int i=0; i<N; i++)
			A[i] = sc.nextInt();
		
		boolean[] b = new boolean[1001];
		Arrays.fill(b, true);
		for(int i=2; i<=500; i++) {
			if(b[i]) {
				for(int j=i+i; j<=1000; j+=i)
					b[j]=false;
			}
		}
		ArrayList<Integer> prime = new ArrayList<>();
		for(int i=2; i<=1000; i++)
			if(b[i])
				prime.add(i);

		HashSet<Integer> factor = new HashSet<>();
		long gcd = A[0];
		boolean isPairwiseCoprime = true;
		for(int i=1; i<N; i++) {
			gcd = gcd(gcd, A[i]);
			for(int p : prime) {
				if(A[i]<p)
					break;
				if(A[i]%p==0) {
					if(factor.contains(p)) {
						isPairwiseCoprime = false;
						break;
					}
					while(A[i]%p==0)
						A[i]/=p;
					factor.add(p);
				}
			}
			if(A[i]>=2) {
				if(factor.contains(A[i])) {
					isPairwiseCoprime = false;
				} else {
					factor.add(A[i]);
				}
			}
		}
		
		if(isPairwiseCoprime) {
			System.out.println("pairwise coprime");
		} else if(gcd==1) {
			System.out.println("setwise coprime");
		} else {
			System.out.println("not coprime");
		}
		
		sc.close();
	}
	
	static long gcd(long a, long b) {
		return a==0 ? b : gcd(b%a, a);
	}
}

