题目描述

现在给你$n$个点，每个点上有一个数值$a_i$。

两个点$(i, j)$之间可以连一条无向边，当且仅当$a_i$是$a_j$的整数倍，或者$a_j$是$a_i$的整数倍。

你的任务是从$n$个点选出一个点数量最多的点集$S$，使得点集$S$中的任意两个点之间都具有一条无向边。求出这个点集大小。

输入格式

第一行一个整数$n$，表示给定点的数量$n$。

接下来$n$个正整数$a_1 \sim a_n$，表示第一个点到第$n$个点上的数值。

输出格式

一行一个正整数，表示最多能选几个点到点集中。

6
2 1 7 9 6 2

4

样例解释

可以选择[2, 1, 6, 2]，不难发现这四个数字中任意两个数字总能描述成其中一个是另一个的倍数。此时选出的点集大小为4个点。

数据规模与约定

每组数据点10分，共10组数据。

大样例

大样例下载