DMOPC '21 Contest 4 P2 - Festive Groups

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

The citizens of Dmojistan are arranging a Christmas gathering! The -th citizen has a jolliness of , 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 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.

Input Specification

The first line contains an integer .

The second line contains integers .

Output Specification

Output a single integer, the answer to the problem.

Sample Input

7
8 3 15 10 6 4 16

Sample Output

3

Explanation

The citizens may be divided into festive groups as follows: .