该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

zwj最近一直在苦恼为什么自己数学这么差，于是他想让你帮帮他解决一个经典的数学问题。

题目描述

给定一个包含 n 个正整数的列表，zwj 想从中选出尽可能多的整数，使得这些整数的最大公约数（GCD）不为 1。

输入格式

一个正整数 $n$，代表列表中元素个数。

一个长度为 $n$ 的正整数数组$a$，其中$1 \le n,a_i \le 10^6$。

输出格式

一个整数，表示最多可以选出多少个数，使得这些数的 GCD 不为 1。

样例 #1

样例输入 #1

5
2 4 6 8 10

样例输出 #1

5

样例 #2

样例输入 #2

3
1 3 6

样例输出 #2

2