Longest Factor Chain

You are given N ingredients with associated weights. Your task is to determine the length of the longest factor chain that can be constructed from these weights.

A factor chain is a sequence of numbers from the given list such that for any two numbers \(a\) and \(b\) in the chain, at least one of the following holds:

$$a\mid b \quad \text{or} \quad b\mid a$$

The chain does not have to use consecutive numbers from the input, and the order of the chain is determined by sorting the weights in non-decreasing order. The goal is to find the maximum possible length of such a chain.

inputFormat

The input is read from stdin and consists of two lines. The first line contains an integer (N) (the number of ingredients). The second line contains (N) space-separated integers, representing the weights of the ingredients.

outputFormat

The output, written to stdout, is a single integer denoting the length of the longest factor chain.## sample

4
3 6 2 18

3