You are now examining a unique method to sort a sequence of numbers in increasing order. The method only allows swapping of two numbers that have a common prime factor. For example, a sequence [6, 4, 2, 3, 7] can be sorted using the following steps.
Step 0: 6 4 2 3 7 (given sequence)
Step 1: 2 4 6 3 7 (elements 6 and 2 swapped)
Step 2: 2 6 4 3 7 (elements 4 and 6 swapped)
Step 3: 2 3 4 6 7 (elements 6 and 3 swapped)


Depending on the nature of the sequence, however, this approach may fail to complete the sorting. You have given a name "Coprime sort" to this approach and are now examining if a given sequence is coprime-sortable.

Make a program to determine if a given sequence can be sorted in increasing order by iterating an arbitrary number of swapping operations of two elements that have a common prime number.



Input

The input is given in the following format.


$N$
$a_1$ $a_2$ $...$ $a_N$


The first line provides the number of elements included in the sequence $N$ ($2 \leq N \leq 10^5$). The second line provides an array of integers $a_i$ ($2 \leq a_i \leq 10^5$) that constitute the sequence.

Output

Output "1" if the sequence is coprime-sortable in increasing order, or "0" otherwise.

Examples

Input

5
6 4 2 3 7


Output

1


Input

7
2 9 6 5 6 7 3


Output

0
#include<iostream>
#include<algorithm>
#include<deque>
#include<set>
using namespace std;
#define MAX_N 100100


int par[MAX_N * 2 + 10];
int myrank[MAX_N * 2 + 10];
int n, a[MAX_N * 2 + 10];
deque<int> v[MAX_N*2+10];
set<int> s;

void init(int n){
	for(int i = 0; i < n; i++){
		par[i] = i;
		myrank[i] = 0;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	
	if(myrank[x] < myrank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if(myrank[x] == myrank[y]) myrank[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}

int main(){
	
	init(MAX_N*2+10);
	
	cin>>n;
	
	for(int i = 0; i < n; i++){
		cin>>a[i];
		int n = a[i];
		a[i] += MAX_N;
		for(int j = 2; j * j <= n; j++){
			if(n%j == 0){
				// cout<<j<<endl;
				unite(j,a[i]);
				while(n%j == 0){
					n/=j;
				}
			}
		}
		if(n != 1){
			unite(n,a[i]);
			// cout<<n<<endl;
		}
	}
	
	for(int i = 0; i < n; i++){
		// cout<<find(a[i])<<endl;
		v[find(a[i])].push_back(a[i]);
		s.insert(find(a[i]));
	}
	for(int y : s){
		sort(v[y].begin(), v[y].end());
	}
	for(int i = 0; i < n; i++){
		a[i] = v[find(a[i])].front();
		v[find(a[i])].pop_front();
		if(i&&a[i-1] > a[i]){
			cout<<0<<endl;
			return 0;
		}
		// cout<<a[i]-MAX_N<<endl;
	}
	
	cout<<1<<endl;
	
	return 0;
}
