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

public class D_Fibonacciish {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
    }

    private static class Solver {
        private int longest(HashMap<Integer, Integer> cnt, int a, int b, int length) {
            int next = a + b;
            if (cnt.getOrDefault(next, 0) == 0) return length;
            cnt.put(next, cnt.get(next) - 1);
            int longest = longest(cnt, b, next, length + 1);
            cnt.put(next, cnt.get(next) + 1);
            return longest;
        }

        private void solve(InputReader inp, PrintWriter out) {
            int n = inp.nextInt();
            ArrayList<Integer> start = new ArrayList<>();
            HashMap<Integer, Integer> cnt = new HashMap<>();
            HashMap<Integer, Integer> total = new HashMap<>();
            for (int i = 0; i < n; i++) {
                int value = inp.nextInt();
                if (!cnt.containsKey(value)) {
                    start.add(value);
                    cnt.put(value, 1);
                    total.put(value, 1);
                } else {
                    cnt.put(value, cnt.get(value) + 1);
                    total.put(value, total.get(value) + 1);
                }
            }
            int res = 2;
            for (int i = 0; i < start.size(); i++) {
                for (int j = 0; j < start.size(); j++) {
                    int a = start.get(i);
                    int b = start.get(j);
                    if (a == b && cnt.get(a) <= 1) continue;

                    cnt.put(a, cnt.get(a) - 1);
                    cnt.put(b, cnt.get(b) - 1);

                    res = Math.max(res, longest(cnt, a, b, 2));

                    cnt.put(a, cnt.get(a) + 1);
                    cnt.put(b, cnt.get(b) + 1);
                }
            }
            out.print(res);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}