GL is playing a new card game he invented, called the Greatest Common Divisor Card Game (GCDCG). Initially, he has $N$ cards, where the $i$-th card has the number $A_i$ on it. In the $j$-th round, he must pick one of the remaining cards and discard it. If the greatest common divisor of all the discarded card numbers is a multiple of $j$, he can proceed to the next round. If he runs out of cards or cannot satisfy this requirement, the game is over. GL now wonders: what is the maximum number of rounds he can play?
Input
The first line of input contains a single integer $N$.
The second line contains $N$ integers, where the $i$-th integer is $A_i$.
Output
Output a single integer — the maximum number of rounds he can play.
Constraints
For all test cases: $1 \le N \le 10^5$, $1 \le A_i \le 10^9$
Subtask 1 (30%): $1 \le N \le 10$
Subtask 2 (30%): $1 \le N \le 1000$
Subtask 3 (40%): No additional constraints
Sample Test Cases
| Input | Output | |
|---|---|---|
| 6 1 2 3 4 6 12 |
3 | |
| In the $1$-st round, GL can choose $6$, then $\gcd(6) = 6$, which is a multiple of $1$. In the $2$-nd round, GL can choose $12$, then $\gcd(6, 12) = 6$, which is a multiple of $2$. In the $3$-rd round, GL can choose $3$, then $\gcd(6, 12, 3) = 3$, which is a multiple of $3$. It can be shown that this is the best GL can do. |
||
Scoring: Per Subtask
Authored by wy23493
Appeared in WYHK 2025 Mini Contest 3