Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if

1. the sequence consists of at least two elements
2. $*f*_{0}$ and $*f*_{1}$ are arbitrary
3. $*f*_{*n* + 2} = *f*_{*n* + 1} + *f*_{*n*}$ for all $*n* ≥ 0$.

You are given some sequence of integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.

Input

The first line of the input contains a single integer $*n*$ ($2 ≤ *n* ≤ 1000$) — the length of the sequence $*a*_{*i*}$.

The second line contains $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($|*a*_{*i*}| ≤ 10^{9}$).

Output

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.

Note

In the first sample, if we rearrange elements of the sequence as $- 1$, $2$, $1$, the whole sequence $*a*_{*i*}$ would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is , , , , $28$.