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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		PrimeNumberGenerator pg = new PrimeNumberGenerator();
		int n = sc.nextInt();
		int a[] = new int[n];
		int a2[] = new int[n];

		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();
			a2[i] = a[i];
		}

		int count[] = new int[1_000_001];
		boolean pc = true;
		for(int i = 0; i < n; i++){
//			System.out.println("i = "+i);
			if(pg.isPrime(a[i])){
				if(count[a[i]] > 0){
//					System.out.println(a[i] + " already appeared");
					pc = false;
					break;
				}
				else {
					count[a[i]]++;
				}
			}

			else {
				int div = 2;
				boolean firstCheck = true;
				while(a[i] > 1){
					if(a[i] % div == 0){
						if(firstCheck && count[div] > 0){
//							System.out.println(div + " already appeared");
							pc = false;
							break;
						}
						else {
							a[i] /= div;
							count[div]++;
							firstCheck = false;
						}
					}
					else {
						div++;
						firstCheck = true;
					}
				}

				if(!pc){
					break;
				}
			}
		}

		if(pc) {
			System.out.println("pairwise coprime");
			return;
		}

		int result = a2[0];

		for(int i = 1; i < n; i++){
			result = gcd(a2[i], result);
		}

		if(result == 1){
			System.out.println("setwise coprime");
		}
		else {
			System.out.println("not coprime");
		}
	}

	static int gcd(int a, int b){
        int tmp;

        while (a % b != 0)
        {
            tmp = b;
            b = a % b;
            a = tmp;
        }
        return b;
    }
}

class PrimeNumberGenerator {
    private final int N = 1000000;
    private boolean[] isPrime= new boolean[N + 1];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;

        int limit = (int)Math.sqrt(N);
        for(int i = 2; i <= limit ; i++){

            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= N; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
        return isPrime[index];
    }
}