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<bits/stdc++.h>
using namespace std;

class UnionFind{
private:
    std::vector<int> par, sizes;
public:
    UnionFind() = delete;
    UnionFind(int sz) : par(sz), sizes(sz, 1){
        for(int i = 0; i < sz; i++){
            par[i] = i;
        }
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y) return false;

        if(sizes[x] < sizes[y]) swap(x, y);
        sizes[x] += sizes[y];
        sizes[y] = 0;
        par[y] = x;
        return true;
    }
    int find(int x){
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }

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

    int size(int x){
        return sizes[find(x)];
    }
};

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    vector<bool> num_table(100100, 0);
    vector<int> prime;

    for(int i = 2; i*i < 100100; i++){
        if(num_table[i]) continue;
        for(int j = i+i; j < 100100; j += i){
            num_table[j] = i;
        }
    }

    for(int i = 2; i < 100100; i++){
        if(num_table[i] == 0) prime.emplace_back(i);
    }

    UnionFind uf(100100 + N);

    for(int i = 0; i < N; i++){
        uf.unite(N + A[i], i);
        for(int j = 0; prime[j] < A[i] && j < prime.size(); j++){
            if(A[i] % prime[j] == 0) {
                uf.unite(N + prime[j], i);
            } 
        }
    }

    sort(A.begin(), A.end());

    bool can = true;
    for(int i = 0; i < N; i++){
        can &= uf.is_same(N + A[i], i);
    }

    cout << can << endl;
}
