D. The World Turned Upside Down
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The world has turned upside down!

In this reversal of roles, we need your help to write a problem!

The problem goes like this: I start with the number 1. Then, I can apply a sequence of operations, where an operation is just multiplying my current number by any positive integer $$$k$$$. For example, I can select $$$k = 3$$$, acquiring the number $$$1 \times 3 = 3$$$. Then I can select a new $$$k = 4$$$, acquiring the number $$$3 \times 4 = 12$$$. Then I select $$$k = 2$$$, acquiring the number $$$12 \times 2 = 24$$$. This results in the sequence of numbers $$$[1, 3, 12, 24]$$$.

My boss (Bennett) has provided me with a list of $$$N$$$ of his favorite numbers; for my problem, I need to find sequences that contain as many of his favorite numbers as possible.

If I create the perfect sequence, how many of Bennett's favorite numbers can I include?

Input

The first line contains a single integer $$$N\ (1 \le N \le 10^3)$$$, denoting the number of Bennett's favorite numbers.

The second line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^{18}$$$), representing the $$$N$$$ target numbers. All $$$a_i$$$ are guaranteed to be distinct.

Output

Output a single integer, the maximum number of favorite numbers you can acquire in a single sequence.

Example
Input
4
2 6 10 12
Output
3
Note

One possible sequence is $$$[1, 2, 6, 12]$$$, which attains 3 of Bennett's favorite numbers.