You are given a sequence of integers A of length n. You need to find a subsequence A' of A such that every element a'_{i} is divisible by the previous element a'_{i-1}.
A subsequence is formed by removing some elements from the sequence without changing the relative order of the remaining elements.
What is the minimum number of elements you need to delete?
Input
The first line contains the integer n (1 \le n \le 8000).
The second line contains n integers (-10^9 \le a_i \le 10^9).
Output
Print the minimum number of elements that must be deleted.
Examples
| standard input | standard output |
|---|
| 6
3 2 6 18 12 36
| 2
|
| 4
1 -4 16 -64
| 0
|
Note
In the first example, after removing two elements, we can obtain a valid subsequence such as (3, 6, 18, 36) or (2, 6, 12, 36).
Note that zero is divisible by any number, but no number is divisible by zero.