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. f0 and f1 are arbitrary 
  3. fn + 2 = fn + 1 + fn for all n ≥ 0. 



You are given some sequence of integers a1, a2, ..., an. 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 ai.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 109).

Output

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

Examples

Input

3
1 2 -1


Output

3


Input

5
28 35 7 14 21


Output

4

Note

In the first sample, if we rearrange elements of the sequence as  - 1, 2, 1, the whole sequence ai would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is <image>, <image>, <image>, <image>, 28.
#!/usr/bin/env python3

n = int(input())
a = [int(x) for x in input().split()]

sorted_a = sorted(a)
dict_a = {}
for x in a:
    if not x in dict_a:
        dict_a[x] = 1
    else:
        dict_a[x] += 1

sorted_uniq_a = sorted(dict_a.keys())

max_fib_prefix = [a[0], a[1]]
for i in range(0, len(sorted_uniq_a)):
    for j in range(0, len(sorted_uniq_a)):
        if i != j or dict_a[sorted_uniq_a[i]] > 1:
            if sorted_uniq_a[i] + sorted_uniq_a[j] > sorted_uniq_a[-1]:
                break

            fib_prefix = [sorted_uniq_a[i], sorted_uniq_a[j]]
            dict_a[sorted_uniq_a[i]] -= 1
            dict_a[sorted_uniq_a[j]] -= 1

            while True:
                next_fib = fib_prefix[-1] + fib_prefix[-2]
                if not next_fib in dict_a or dict_a[next_fib] == 0:
                    break
                fib_prefix.append(next_fib)
                dict_a[next_fib] -= 1

            for x in fib_prefix:
                dict_a[x] += 1

            if len(fib_prefix) > len(max_fib_prefix):
                max_fib_prefix = fib_prefix

print(len(max_fib_prefix))
