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

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int N=1000000,i,j; boolean c[]=new boolean[N+1];
        for(i=2;i<=N;i++)
        if(!c[i])
        for(j=2*i;j<=N;j+=i)
        c[j]=true;

        ArrayList<Integer> pr=new ArrayList<>();
        for(i=2;i<=N;i++)
        if(!c[i]) pr.add(i);

        HashMap<Integer,Integer> hm=new HashMap<>();
        int sz=pr.size(),ar[]=new int[sz];
        for(i=0;i<sz;i++)
        hm.put(pr.get(i),i);

        int n=Integer.parseInt(bu.readLine());
        int a[]=new int[n];
        String s[]=bu.readLine().split(" ");
        for(i=0;i<n;i++)
        {
            a[i]=Integer.parseInt(s[i]);
            int x=a[i];
            for(j=2;j*j<=x;j++)
            if(x%j==0)
            {
                ar[hm.get(j)]++;
                while(x%j==0) x/=j;
            }
            if(x>=2) ar[hm.get(x)]++;
        }

        int max=0;
        for(i=0;i<sz;i++)
        max=Math.max(max,ar[i]);
        if(max<2) {System.out.print("pairwise coprime"); return;}

        int g=a[0];
        for(i=1;i<n;i++)
        g=gcd(g,a[i]);
        if(g==1) sb.append("setwise coprime");
        else sb.append("not coprime");
        System.out.print(sb);
    }

    static int gcd(int a,int b)
    {
        int t;
        while(b!=0)
        {
            t=b;
            b=a%b;
            a=t;
        }
        return a;
    }
}
