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.*;

public class Fibsh {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Long> nums = new ArrayList<>();
        int numZeros = 0;

        int t = sc.nextInt();
        for (int i=0; i< t; i++) {
            long ss = sc.nextLong();
            if (ss == 0)
               numZeros++;
            else
                nums.add(ss);
        }

        if (numZeros == 1) {
            nums.add(0L);
            numZeros--;
        }

        Map<Long, Integer> numsSet = new HashMap<>();
        for (Long n : nums) {
            if (numsSet.containsKey(n)) {
                numsSet.put(n, numsSet.get(n) + 1);
            } else {
                numsSet.put(n, 1);
            }
        }

        int len = 0;
        Map<String, Integer> dp = new HashMap<>();
        for (int i=0; i< nums.size(); i++) {
            for (int j=0; j< nums.size(); j++) {

                if (dp.containsKey(nums.get(i) + "," + nums.get(j))) {
                    continue;
                }

                if (i != j) {
                    long prev1 = nums.get(i);
                    long prev2 = nums.get(j);
                    long target = prev1 + prev2;
                    int tmp = 2;

                    Map<Long, Integer> used = new HashMap<>();
                    used.put(prev1, 1);
                    used.put(prev2, 1);
                    int zeros = numZeros;

                    while (numsSet.containsKey(target) && (!used.containsKey(target) || used.get(target) < numsSet.get(target))
                            || (target == 0 && zeros > 0)) {

                        if (target == 0) {
                            zeros--;
                        }
                        int count = used.get(target) != null ? used.get(target) : 0;
                        used.put(target, count+1);
                        tmp++;
                        prev1 = prev2;
                        prev2 = target;
                        target = prev1 + prev2;
                    }

                    if (tmp > len) {
                        len = tmp;
                    }

                    dp.put(nums.get(i) + "," + nums.get(j), len);
                }
            }
        }

        System.out.println(Math.max(len, numZeros));

    }
}
