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 ArrayList<Long> primes;
	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		int n = Integer.parseInt(bf.readLine());
 		primes = new ArrayList<Long>();
 		StringTokenizer st = new StringTokenizer(bf.readLine());
 		long[] array = new long[n];
 		long gcd = array[0];
 		for(int j= 0 ;j<n;j++){
 			array[j] = Long.parseLong(st.nextToken());
 			gcd = gcd(array[j], gcd);
 		}
 		boolean ans = true;
 		if (gcd == 1){
	 		sieveOfEratosthenes(1000001);
	 		
	 		Set<Long> p = new HashSet<Long>();
	 		for(int j =0;j<n;j++){
	 			if (array[j] == 1)
	 				continue;
	 			boolean prime = true;
	 			for(long pr : primes){
	 				if (pr*pr > array[j] && prime){
	 					if (p.contains(array[j])){
	 						ans = false;
	 						break;
	 						
	 					}
	 					else{
		 					p.add(array[j]);
		 					break;
	 					}
	 				}
	 				else if (pr*pr > array[j]){
	 					break;
	 				}
	 				if (pr*pr == array[j]){
	 					if (p.contains(pr)){
	 						ans = false;
	 						break;
	 					}
	 					else{
	 						p.add(pr);
	 						prime = false;
	 					}
	 				}
	 				else if (array[j]%pr == 0){
	 					if (p.contains(pr)){
	 						ans = false;
	 						break;
	 					}
	 					else if (p.contains(array[j]/pr)){
	 						ans = false;
	 						break;
	 					}
	 					else{
	 						p.add(pr);
	 						p.add(array[j]/pr);
	 						prime = false;
	 					}
	 				}
	 			}
	 			if (!ans)
	 				break;
	 		}
 		}
 		
 		if (gcd > 1)
 			out.println("not coprime");
 		else if (ans)
 			out.println("pairwise coprime");
 		else
 			out.println("setwise coprime");
	 		
 		out.close();
 		
 		
 		
 	}
	public static long gcd(long a, long b){ 
	      if (b == 0) 
	        return a; 
	      return gcd(b, a % b);  
	}
	public static void sieveOfEratosthenes(int n) {  
        boolean prime[] = new boolean[n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) { 
        	if(prime[p]){ 
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
        for(int i = 2; i <= n; i++){ 
            if(prime[i] == true) 
                primes.add((long)(i));
        } 
    }
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	


