Bash's Big Day

Bash 已经踏上了成为最伟大的口袋妖怪大师的旅程。为了得到他的第一个口袋妖怪，他去了 Zulu 教授的实验室。由于 Bash 是 Zulu 教授最喜欢的学生，Zulu 允许他从实验室里取出任意数量的口袋妖怪。 但是 Zulu 警告他，每个小精灵都有一个力量值，例如 $k(k>1)$ 个小精灵在一起，它们的力量值为 $s_1,s_2,\dots,s_k$，如果 $\gcd(s_1,s_2,\dots s_k)=1$（见 $\gcd$ 的定义注释），它们之间就会互相打架。 Bash 作为一个聪明的人，不希望他的口袋妖怪互相斗争。然而，他也想最大化他从实验室里带走的神奇宝贝的数量。你能帮 Bash 找出他能带走的最大数量的口袋妖怪吗？ **注意：口袋妖怪不能与自己战斗。** ### 输入格式 输入包含两行。 第一行一个整数 $n(1\le n \le 10^5)$，表示实验室中的小精灵总数。 第二行 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 个小精灵的力量值 $s_i(1 \le s_i \le 10^5)$。 ### 输出格式 一行包含一个整数，表示能拿走的小精灵数量最大值。

Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases. But Zulu warns him that a group of $ k>1 $ Pokemon with strengths $ {s_{1},s_{2},s_{3},...,s_{k}} $ tend to fight among each other if $ gcd(s_{1},s_{2},s_{3},...,s_{k})=1 $ (see notes for $ gcd $ definition). Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? Note: A Pokemon cannot fight with itself.

The input consists of two lines. The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ), the number of Pokemon in the lab. The next line contains $ n $ space separated integers, where the $ i $ -th of them denotes $ s_{i} $ ( $ 1<=s_{i}<=10^{5} $ ), the strength of the $ i $ -th Pokemon.

Print single integer — the maximum number of Pokemons Bash can take.

3
2 3 4

2

5
2 3 4 6 7

3

$ gcd $ (greatest common divisor) of positive integers set $ {a_{1},a_{2},...,a_{n}} $ is the maximum positive integer that divides all the integers $ {a_{1},a_{2},...,a_{n}} $ . In the first sample, we can take Pokemons with strengths $ {2,4} $ since $ gcd(2,4)=2 $ . In the second sample, we can take Pokemons with strengths $ {2,4,6} $ , and there is no larger group with $ gcd≠1 $ .