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.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 static List<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
		 static int a_dist[];
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);
	        int N = sc.nextInt();	
	        long[] a = new long[N];
	        for (int i=0 ; i<N; i++) {
	            a[i] = Long.parseLong(sc.next());
	        }

	        int H = 1000005;
	        int[] m = new int[H];
	        int[] p = new int[H];
	        int k=0;
	        m[1]=1;
	        for(int i=2;i<H;i++) {
	        	if(m[i]==0) {
	        		m[i]=1;
	        		p[k]=i;
	        		k++;
	        		for(int j=i+i;j<H;j=j+i) {
	        			m[j]=i;
	        		}
	        	}
	        }		        
	        
	        int[] m2 = new int[1000005];
	        String ans = "pairwise coprime";
	        for(int i=0;i<N;i++) {
	        	while(a[i]!=1) {
	        		if(m[(int)a[i]]!=1) {
	        				int tmp =(int)a[i];
		        			m2[m[tmp]]++;
		        			while(a[i]%m[tmp]==0) {
		        				a[i]=a[i]/m[tmp];
		        			}
	        		} else {
	        			m2[(int)a[i]]++;
	        			a[i]=1;
	        		}
	        	}
	        }
	        
	        for(int i=0;i<1000005;i++) {
	        	if(m2[i]>1)ans = "setwise coprime";
	        	if(m2[i]==N) {
	        		ans = "not coprime";
	        		break;
	        	}
	        }
	        
	        System.out.println(ans);
		 }
		 
	}