题目描述

人这一生，总要走过一些路。

有些路平坦，走过去时甚至来不及记住两旁的风景；有些路却像一列绵长的山丘，起伏不定，沉默地横在面前。

少年时，总以为翻过一座山，就能看见答案；后来才明白，真正困难的从来不是抵达终点，而是在广阔的天地间，决定先去哪里，又该带走什么。

如今，旅人，你正面对着这样一片广袤的土地。

这片土地上散落着 $N$ 座城。第 $i$ 座城里，放着一个整数 $a_i$。你得到了一张神奇的地图，可以自由决定拜访这 $N$ 座城的顺序。每座城最多只能拜访一次。在经过每座城时，你都可以做出一个决定：

• 取走这座城中的数字；
• 或者什么也不取，继续前行。

但旅途并不允许毫无节制地收集一切。

如果你此前已经取走了一些数，那么当你想取走当前城市中的数 $a_i$ 时，必须满足以下条件：

• $a_i$ 必须是你上一个取走的数的倍数。

最开始时，你手中没有任何数字，因此你第一次想取走某个数时，一定可以直接取走。

请你计算：在合理规划拜访顺序的前提下，最多可以取走多少个数。

输入格式

从文件 $\textit{\textbf{hill.in}}$ 中读入。

第一行一个整数 $N$，表示城市的数量。

第二行包含 $N$ 个整数 $a_1,a_2,\dots,a_N$，表示每座城中的数字。

输出格式

输出到文件 $\textit{\textbf{hill.out}}$ 中。

输出一行一个整数，表示最多能够取走的数字个数。

输入输出样例

输入输出样例

输入样例 1

3
2 6 3

输出样例 1

2

样例 1 说明

一种最优方案如下：

• 在第一座城取走 $2$；
• 在第二座城取走 $6$，因为 $6$ 是此前已取数字 $2$ 的倍数；
• 到第三座城时，不能再取走 $3$，因为 $3$ 既不是 $2$ 和 $6$ 的公共倍数，也不是它们的公共约数。

因此，最多只能取走 $2$ 个数。

样例 2

见下发文件中的 $\textbf{\textit{hill2.in}}$ 与 $\textbf{\textit{hill2.out}}$。

数据范围和约定

对于 $20\%$ 的数据，满足 $1 \le N \le 10$。

对于 $50\%$ 的数据，满足 $1 \le N \le 1000$。

对于另外 $20\%$ 的数据，满足所有 $a_i$ 互不相同。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^6$，$1 \le a_i \le 10^6$。