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 Fib {
    public static void main(String [] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();

        HashMap<Long, Integer> set = new HashMap<Long, Integer>();
        long[] nums = new long[n];
        int numzeroes = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = s.nextInt();

            if (!set.containsKey(nums[i])) {
                set.put(nums[i], 0);
            }
            set.put(nums[i], set.get(nums[i]) + 1);
            if (nums[i] == 0) {
                numzeroes++;
            }
        }


        Arrays.sort(nums);

        int max = numzeroes;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                long one = nums[i];
                long two = nums[j];
                if (one == 0 && two == 0) {
                    continue;
                }
                HashMap<Long, Integer> chosen = new HashMap<Long, Integer>();
                if (one == two) {
                    chosen.put(one, 2);
                }
                else {
                    chosen.put(one, 1);
                    chosen.put(two, 1);
                }

//                System.out.println(one);
//                System.out.println(two);
                int size = 2;
                while (true) {
                    long next = one + two;
//                    System.out.println(next);
                    if (set.containsKey(next)) {
                        if (chosen.containsKey(next)) {
                            if ((set.get(next) - chosen.get(next) > 0)) {
                                size++;
                                chosen.put(next, chosen.get(next) + 1);
                                one = two;
                                two = next;
                                continue;
                            } else {
                                break;
                            }
                        } else {
                            size++;
                            chosen.put(next, 1);
                            one = two;
                            two = next;
                            continue;
                        }
                    }
                    break;
                }
                max = Integer.max(size, max);
//                System.out.println(chosen + " " + max);
            }
        }


        System.out.println(max);

    }
}
