For a given numerical sequence a1, a2, ..., an want to find the maximum length of multiple successive subsequence. In order to consistently fold subsequence ak1, ak2, ..., akt (k1 <... <= i <= t (the statement "a | b" is equivalent to "b multiply a") . Subsequence of a single element relies on multiple sequence definition.
Input In the first line of the input file is written one positive integer N (1 <= N <= 1000) - the number of numbers in the original sequence. This is followed by N numbers of modulus not greater than 109 - the sequence. Output Display only the number equal to the desired number.