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.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	int N;
	int[] A;
	Set<Integer>[] sets;
	int[] filter;

	Main(BufferedReader in) throws IOException {
		N = Integer.parseInt(in.readLine());
		String[] tokens = in.readLine().split(" ");
		A = new int[N];
		for (int i = 0; i < N; ++i) {
			A[i] = Integer.parseInt(tokens[i]);
		}
		Arrays.sort(A);
		filter = new int[A[N - 1] + 1];
		Arrays.fill(filter, -1);
		filter[1] = 1;
		for (int step = 2; step <= A[N - 1]; ++step) {
			for (int i = step; i <= A[N - 1]; i += step) {
				if (filter[i] < 0) {
					filter[i] = step;
				}
			}
		}
		sets = new Set[N];
		for (int i = 0; i < N; ++i) {
			sets[i] = getYakusuu(A[i]);
		}
	}

	void show() {
		for (int i = 0; i < N; ++i) {
			System.out.print(i + ": ");
			for (Integer val : sets[i]) {
				System.out.print(val + " ");
			}
			System.out.println("");
		}
	}

	Set<Integer> getYakusuu(int val) {
		Set<Integer> result = new HashSet<>();
		if (val == 1) {
			return result;
		}
		while (filter[val] != val) {
			result.add(filter[val]);
			val = val / filter[val];
		}
		result.add(val);
		return result;
	}

	int gcd(int large, int small) {
		if (large < small) {
			return gcd(small, large);
		}
		if (large % small == 0) {
			return small;
		} else {
			return gcd(small, large % small);
		}
	}

	boolean isSetwise() {
		int gcd = gcd(A[0], A[1]);
		for (int i = 2; i < N; ++i) {
			gcd = gcd(gcd, A[i]);
		}
		if (gcd == 1) {
			return true;
		} else {
			return false;
		}
	}

	boolean isPairwise() {
		int count = 0;
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; ++i) {
			count += sets[i].size();
			list.addAll(sets[i]);
		}
		if ((long) count == list.stream().distinct().count()) {
			return true;
		} else {
			return false;
		}
	}

	void calc() {
		if (isSetwise()) {
			if (isPairwise()) {
				System.out.println("pairwise coprime");
			} else {
				System.out.println("setwise coprime");
			}
		} else {
			System.out.println("not coprime");
		}
	}

	void showResult() {
		// show();
	}
}