C. Sour Straws
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anisha loves sour candy! Her favorite sour snack are sour straws

Anisha has come into possession of $$$n$$$ sour straws, but she is actually very picky about how she eats them. In particular, each of her sour straws has an associated length: the $$$i^\text{th}$$$ of her sour straws has a length of $$$l_i$$$ inches.

Anisha can choose to eat a subset of her sour straws if each of the sour straws in the subset has a length divisible by all shorter sour straws included in the subset. More formally, if her subset of sour straws is denoted as $$$S \subseteq \{1, 2, \dots, n\}$$$, then $$$\forall\ i, j \in S,\ l_i \leq l_j \implies l_i \mid l_j$$$ must hold (where $$$a \mid b$$$ means $$$b$$$ is divisible by $$$a$$$).

Despite her pickiness, Anisha wants to eat as many sour straws as possible. As such, she wants you to compute the largest subset of her sour straws that she can eat without violating her condition mentioned above.

Input

The input will begin with a single line containing a single integer $$$n\ (1 \leq n \leq 10^3)$$$, denoting the number of sour straws Anisha has.

The next line will contain $$$n$$$ space-separated integers $$$l_1, l_2, \dots, l_n\ (1 \leq l_i \leq 2 \cdot 10^9)$$$, denoting the lengths of each of Anisha's sour straws, in inches.

Output

The output should consist of a single line containing a single integer, the size of the largest possible subset of sour straws that Anisha can eat at once without violating her pickiness condition.

Examples
Input
5
2 7 5 4 8
Output
3
Input
5
10 10 10 10 10
Output
5