题目描述

给定$N$个非负整数，请你选出尽可能多的数，要求选出的数存在不是$1$的公约数。求最多可以选出数量的最大值。例如：$2、3、 4、 6、 7$ 其中最多可以选出$3$个数 $2、 4、 6$

输入

第一行，一个整数$N$。
第二行 $n$个非负整数$A_i$

输出

一个整数。如果找不到两个具有不是$1$的公约数，那么输出$1$。

样例输入

5
2 3 4 6 7

样例输出

3

提示

$N<=10^6$
$A_i<=10^5$