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.
import java.util.*;
import java.math.*;

public class Template {

    static long maxlen = 0;
    static Map<Long, Integer> nums = new HashMap<Long, Integer>();
    static long[] arr;
    static Set<String> memo = new HashSet<String>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            if (nums.containsKey(a)) {
                nums.put(a, nums.get(a)+1);
            } else {
                nums.put(a, 1);
            }
            arr[i] = a;
        }
        sc.close();

        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
		if (memo.contains(arr[i] + " " + arr[j])) continue;
		memo.add(arr[i] + " " + arr[j]);
                nums.put(arr[i], nums.get(arr[i])-1);
                nums.put(arr[j], nums.get(arr[j])-1);
                solve(arr[j], arr[i]+arr[j],2);
                solve(arr[i], arr[j]+arr[i],2);
                nums.put(arr[i], nums.get(arr[i])+1);
                nums.put(arr[j], nums.get(arr[j])+1);
            }
        }

        System.out.println(maxlen);
    }

    static void solve(long last, long lookingfor, long len) {
        maxlen = Math.max(maxlen, len);
        if (nums.containsKey(lookingfor)) {
            if (nums.get(lookingfor) > 0) {
                nums.put(lookingfor, nums.get(lookingfor)-1);
                solve(lookingfor, last+lookingfor, len+1);
                nums.put(lookingfor, nums.get(lookingfor)+1);
            }
        }
    }
}