题目描述

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$，它们之间就会互相打架。

Bash 作为一个聪明的人，不希望他的口袋妖怪互相斗争。然而，他也想最大化他从实验室里带走的神奇宝贝的数量。你能帮 Bash 找出他能带走的最大数量的口袋妖怪吗？

注意：口袋妖怪不能与自己战斗。

输入格式

第一行一个整数 $n\ (1\le n \le 10^5)$，表示实验室中的小精灵总数。

第二行 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 个小精灵的力量值 $s_i\ (1 \le s_i \le 10^5)$。

输出格式

一行包含一个整数，表示能拿走的小精灵数量最大值。

3
2 3 4

2

5
2 3 4 6 7

3