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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	
	int[] sosuArr = new int[1_000_000_1];
	
	int[] soinsuArr  = new int[1_000_000_1];

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		makeSosuList();
		int n = fs.nextInt();
		int[] aArr = fs.nextIntArr(n);
		
		
		boolean pairWise = true;
		for(int i = 0; i < n; i++) {
			Set<Integer> soinsuSet = getSoinsuSet(aArr[i]);
			for(Integer soinsu : soinsuSet) {
				if(soinsuArr[soinsu] == 1) {
					pairWise = false;
					break;
				}
				soinsuArr[soinsu]++;
			}
		}
		
		if(pairWise) {
			System.out.println("pairwise coprime");
			return;
		}
		
		int allGcd = gcd(aArr[n-2], aArr[n-1]);
		for(int i = n-3; i >= 0; i--) {
			allGcd = gcd(allGcd, aArr[i]);
		}
		if(allGcd == 1) {
			System.out.println("setwise coprime");
			return;
		}
		
		System.out.println("not coprime");
		
		
	}
	
	
	boolean hasInterSection(Set<Integer> set1, Set<Integer> set2) {
		Set<Integer> left;
		Set<Integer> right;
		
		if(set1.size() < set2.size()) {
			left = set1;
			right = set2;
		}else {
			left = set2;
			right = set1;
		}
		
		for(Integer val : left) {
			if(right.contains(val)) {
				return true;
			}
		}
		
		return false;
	}
	
	
	void makeSosuList() {
		int maxVal = 1_000_000_1;
		int[] arr = sosuArr;
		
		for(int i = 0; i < maxVal; i++) {
			arr[i] = 1;
		}
		
		for(int i = 2; i < maxVal; i++) {
			if(arr[i] > 1) {
				continue;
			}
			
			for(int j = 2; j*i < maxVal; j++) {
				arr[j*i] = i;
			}
		}
	}
	
	public Set<Integer> getSoinsuSet(int val){
		Set<Integer> retSet = new HashSet<>();
		while(val > 1) {
			if(sosuArr[val] == 1) {
				retSet.add(val);
				return retSet;
			}
			int soinsu = sosuArr[val];
			val /= soinsu;
			retSet.add(soinsu);
		}
		
		return retSet;
	}

	public int gcd(int a, int b) {
		if (a < b) {
			int swap = a;
			a = b;
			b = swap;
		}
		int r = a % b;
		while (r != 0) {
			a = b;
			b = r;
			r = a % b;
		}
		return b;
	}

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}
