EOJ Monthly 2017.12 (暨 ECNU 12 月内部选拔)
D. 唐纳德和他的数学老师
单点时限: 1.0 sec
内存限制: 256 MB
唐纳德是一个数学天才。有一天，他的数学老师决定为难一下他。他跟唐纳德说：「现在我们来玩一个游戏。这个游戏总共 $n$ 轮，每一轮我都会给你一个数（第 $i$ 轮给出的数是 $a_i$）。你每次要回答一个数，是我给出的这个数的质因数，并且你说出的数不能重复。」
因为数学老师是刻意为难，所以这个游戏很有可能不可能进行到最后。但是聪明的数学老师早就已经知道这个游戏最多能进行几轮了。现在他把问题抛给了你，想看看你知不知道。
注意，$1$ 不是质数。
输入格式
输入具有如下形式：
$n \
a_1 \ a_2 \ \ldots \ a_n$
第一行一个整数 $n$ ($1 \le n \le 3~000$)。
第二行 $n$ 个整数用空格隔开，$a_1, a_2, \ldots, a_n$ ($2 \le a_i \le 10^6$)。
输出格式
输出游戏最多能进行几轮。
样例
Input
3 7 6 3
Output
3
Input
5 2 2 2 2 2
Output
1
通知
比赛状态发生变化，点 OK 刷新。
通知