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.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(final String args[]) throws Exception {
        final Scanner in = new Scanner(System.in);
        final int count = in.nextInt();
        in.nextLine();

        final int[] values = new int[count];
        final Set<Integer> set = new HashSet<>(count);
        for (int i = 0; i < count; i++) {
            values[i] = in.nextInt();
            set.add(values[i]);
        }

        final HashSet<String> valueSet = new HashSet<>();
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < count; j++) {
                if (i == j) {
                    continue;
                }
                if (set.contains(values[i] + values[j])) {
                    valueSet.add(values[i] + " " + values[j]);
                }
            }
        }
        int max = 2;
        final boolean[] hasUse = new boolean[count];

        for (final String s : valueSet) {
            final String[] split = s.split(" ");
            int a = Integer.valueOf(split[0]);
            int b = Integer.valueOf(split[1]);

            for (int k = 0; k < count; k++) {
                hasUse[k] = false;
            }

            for (int k = 0; k < count; k++) {
                if (values[k] == a && !hasUse[k]) {
                    hasUse[k] = true;
                    break;
                }
            }

            for (int k = 0; k < count; k++) {
                if (values[k] == b && !hasUse[k]) {
                    hasUse[k] = true;
                    break;
                }
            }

            int thisCount = 2;
            while (true) {
                final int c = a + b;
                boolean isFind = false;
                if (set.contains(c)) {
                    for (int k = 0; k < count; k++) {
                        if (values[k] == c && !hasUse[k]) {
                            isFind = true;
                            hasUse[k] = true;
                            break;
                        }
                    }
                }
                if (isFind) {
                    a = b;
                    b = c;
                    thisCount++;
                } else {
                    break;
                }
            }

            max = max < thisCount ? thisCount : max;

        }

        System.out.println(max);
    }
}
			 	  					    	 					   			