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.Scanner;

/**
 * Created by enpingkuang on 2020/9/11 11:31 下午
 */
public class Main {
    private static int[] prime = new int[1000001];
    private static int[] factor = new int[1000005];
    private static boolean[] vis = new boolean[1000001];

    private static int gcd(int a,int b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }

    private static void getPrime(){
        for(int i = 2;i<=1000000;i++){
            if(prime[i] == 1){
                continue;
            }
            factor[i] = i;
            for(int j = 2;j*i<=1000000;j++){
                factor[j * i] = i;
                prime[j*i] = 1;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        getPrime();
        boolean first = true;
        boolean second = false;
        int tmp_gcd = 0;
        for(int i = 0;i<n;i++){
            int x = scanner.nextInt();
            first = resolve(first,x);
            tmp_gcd = gcd(x,tmp_gcd);
            if(tmp_gcd == 1){
                second = true;
            }
        }
        if(first){
            System.out.println("pairwise coprime");
        }else{
            if(second){
                System.out.println("setwise coprime");
            }else{
                System.out.println("not coprime");
            }
        }
    }

    private static boolean resolve(boolean flag,int x){
        if (!flag) {
            return false;
        }
        while (x != 1) {
            if(vis[factor[x]]){
                return false;
            }
            vis[factor[x]] = true;
            int tmp = factor[x];
            x /= factor[x];
            while(x!= 1 && tmp == factor[x]) {
                x /= factor[x];
            }
        }
        return true;
    }
}
