Zealous Zeyu is looking for a brand new set of arms today!
There are arms currently on sale. The arm has a length of 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 ).
Zeyu is looking to replace 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.
The first line will contain one integer, .
The second line will contain integers, , the lengths of the arms.
Read carefully: It is guaranteed that 's prime factors will have a value of less than or equal to . In other words, if where is a unique prime, then .
Output space separated integers, the integer representing the minimum number of unique prime factors for the product of arm lengths in a set.
Subtask 1 [5%]
Subtask 2 [25%]
Subtask 3 [70%]
No further 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