巴什已经踏上了成为最伟大的神奇宝贝大师的旅程。为了获得他的第一只神奇宝贝,他去了祖鲁教授的实验室。由于巴什是祖鲁教授最喜欢的学生,祖鲁允许他从实验室里拿走尽可能多的神奇宝贝。
但 Zulu 警告他,如果 gcd(s1, s2, s3, ..., sk) = 1,则一组 k > 1 个具有 {s1, s2, s3, ..., sk} 优势的 Pokemon 往往会互相争斗(请参阅 gcd 定义的注释)。
巴什很聪明,不希望他的神奇宝贝互相争斗。然而,他也想最大限度地增加他从实验室带走的神奇宝贝的数量。你能帮助 Bash 找出他最多可以携带的 Pokemon 数量吗?
注意:神奇宝贝不能与自己战斗。
输入
输入由两行组成。
第一行包含一个整数n (1 ≤ n ≤ 105),即实验室中神奇宝贝的数量。
下一行包含 n 个空格分隔的整数,其中第 i 个表示 si (1 ≤ si ≤ 105),即第 i 个神奇宝贝的强度。
输出
打印单个整数 — Pokemons Bash 可以容纳的最大数量。
示例
输入 #1
3 2 3 4
输出 #1
2
输入 #2
5 2 3 4 6 7
输出 #2
3
注意
正整数集合 {a1, a2, ..., an} 的 gcd(最大公约数)是整除所有整数 {a1, a2, ..., an} 的最大正整数。
在第一个示例中,我们可以选择强度为 {2, 4} 的 Pokemon,因为 gcd(2, 4) = 2。
在第二个样本中,我们可以选取强度为 {2, 4, 6} 的 Pokemon,并且不存在 gcd ≠ 1 的更大组。