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 \dots \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