Prime Sort

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

inputFormat

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.

outputFormat

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

样例

5
6 4 2 3 7

1