The ~N~ citizens of Dmojistan are arranging a Christmas gathering! The ~i~-th citizen has a jolliness of ~J_i~, and a group of citizens is festive if the smallest jolliness of a citizen in that group is a divisor of the jolliness of every citizen in the group. To ensure that the gathering is as exciting as possible, the ~N~ citizens want to split themselves into some number of groups, where each group is festive and the number of groups is minimized. Please determine the number of groups in such an arrangement.
~1 \le N \le 2 \times 10^6~
~1 \le J_i \le 5 \times 10^6~
Subtask 1 [20%]
~1 \le N \le 2 \times 10^3~
Subtask 2 [80%]
No additional constraints.
The first line contains an integer ~N~.
The second line contains ~N~ integers ~J_1, J_2, \dots, J_N~.
Output a single integer, the answer to the problem.
7 8 3 15 10 6 4 16
The citizens may be divided into ~3~ festive groups as follows: ~[8, 4, 16], [3, 15, 6], ~.