Zealous Zeyu is looking for a brand new set of arms today!

There are $N$ arms currently on sale. The $i^{\text{th}}$ arm has a length of $a_i$ zeyumeters from end to end. For legal and aesthetic reasons, the store refuses to sell you two of the same arm (i.e. two of arm $i$).

Zeyu is looking to replace $k$ of his arms. He prefers sets of arms where the product of its arm lengths contains the minimal number of unique prime factors. He likes to be as prime as possible 😎.

What is the minimal number of unique prime factors of such a set? Zeyu needs to know this in order to make the best possible purchase.

Input Specification

The first line will contain one integer, $N$ $(1\le N\le {10}^5)$.

The second line will contain $N$ integers, $a_i$ $(2\le a_i\le {10}^9)$, the lengths of the arms.

Read carefully: It is guaranteed that $a_i$'s prime factors will have a value of less than or equal to $75$. In other words, if $a_i=b_1^{m_1}\times b_2^{m_2}\times \cdots \times b_k^{m_k}$ where $b_j$ is a unique prime, then $2\le b_j\le 75$.

Output Specification

Output $N$ space separated integers, the $k^{\text{th}}$ $(1\le k\le N)$ integer representing the minimum number of unique prime factors for the product of $k$ arm lengths in a set.

Constraints

Subtask 1 [5%]

$N\le 15$

Subtask 2 [25%]

$N\le 100$

Subtask 3 [70%]

No additional constraints.

Sample Input 1

4
2 20 10 15

Sample Output 1

1 2 2 3

Sample Input 2

3
7 153 10

Sample Output 2

1 3 5