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.*;
import java.io.*;
public class Main  {
    static int maxGCD(int b[], int n) 
	{ 
		int high = 0; 
		for (int i = 0; i < n; i++) 
		{
		    if(b[i]>high)
		    high=b[i];
		}
		int count[]=new int[high + 1]; 
		for (int i = 0; i < n; i++) 
			count[b[i]]++; 
		int c = 0; 
	
		for (int i = high; i >= 1; i--) 
		{ 
			int j = i; 
	
			while (j <= high) 
			{ 
				if (count[j]>0)	 
					c+=count[j];		 
				j += i; 
				if (c == 2)		 
					return i; 
			} 
			c=0; 
		} 
	return 1; 
	}
    static int gcd(int m,int n)
    {
        if(n==0)
        return m;
        else
        return gcd(n,m%n);
    }
    public static void main(String args[]) {
      FastScanner fs=new FastScanner();    
      PrintWriter out=new PrintWriter(System.out);
        
        int n=fs.nextInt();
        int a[]=fs.readArray(n);
        
        int i;
        int sg=gcd(a[0],a[1]);
        for(i=2;i<n;i++)
        {
            sg=gcd(sg,a[i]);
        }
        if(sg!=1)
        {
            out.println("not coprime");
        }
        else
        {
            if(maxGCD(a,n)==1)
            out.println("pairwise coprime");
            else
            out.println("setwise coprime");
        }
        
        out.flush();
        out.close();
    }
	static void ruffleSort(int[] a) {
 		Random random=new Random();
		int n=a.length;
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
}
        class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while (!st.hasMoreTokens())
				try {
				st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		String nextLine(){
		    String str="";
		    try{
		        str=br.readLine();
		    }catch(IOException e){
		        e.printStackTrace(); }
		    return str;
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}