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
//package src.com.jetman.atcoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @description:
 * @author: Jetman
 * @create: 2020-08-29 14:39
 **/
public class Main {

    Scanner sc = new Scanner(System.in);

    long MOD = 1000000000 + 7;
    boolean[] judge;
    List<Integer> prime ;

    void initial(int bound) {
        judge[0] = false;
        judge[1] = false;
        for (int i = 2; i <= bound; i++) {
            judge[i] = true;
        }

        for (int i = 2; i <= bound; i++) {
            if (judge[i]) {
                prime.add(i);
                //倍数不是
                for (int j = 2 * i; j <= bound; j += i) {
                    judge[j] = false;
                }
            }
        }
    }



    List<Integer> divide(int n){
        if (judge[n]) {
            return Arrays.asList(n);
        }
        int tmp = (int) Math.sqrt(n);
        List<Integer> ans = new ArrayList<>();
        int i = 0;
        while (prime.get(i) <= tmp && prime.get(i) <= n){
            int k = prime.get(i);
            if(n%k==0){
                ans.add(k);
                while(n%k==0){
                    n/=k;
                }
            }
            i++;
        }
        if(n>1){
            ans.add(n);
        }
        return ans;
    }

    private void slove() {

        int n = sc.nextInt();

        judge = new boolean[1000002];
        prime = new ArrayList<>();
        initial(1000000);

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] flag = new int[1000002];
        int ans = 1;
        for (int i = 0; i < n ; i++) {
            List<Integer> prime = divide(a[i]);
            for (int j = 0; j < prime.size(); j++) {
                if (ans == 1 && flag[prime.get(j)] > 0) {
                    ans++;
                }
                flag[prime.get(j)]++;
            }
        }
        if (ans == 1) {
            System.out.println("pairwise coprime");
            return ;
        }
        boolean f = Arrays.stream(flag).anyMatch(p -> p >= n);
        System.out.println(f?"not coprime":"setwise coprime");



    }

    public static void main(String[] args) {
        new Main().slove();
    }
}
