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 Solution {
    private BufferedReader in;
    private StringTokenizer line;
    private PrintWriter out;

    private static final int mm = 1000000007;

    public void solve() throws IOException {
        int n = nextInt();
        int[] a = nextIntArray(n);
        Arrays.sort(a);
        HashMap<Integer, Integer> b = new HashMap<>();
        for (int i = 0; i < n; ) {
            int j = i;
            while (i < n && a[i] == a[j]) {
                i++;
            }
            b.put(a[j], i - j);
        }
        int res = 2;
        if (b.containsKey(0)) {
            res = Math.max(res, b.get(0));
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && !(a[i] == 0 && a[j] == 0)) {
                    int first = a[i];
                    int second = a[j];
                    HashMap<Integer, Integer> c = new HashMap<>();
                    addAndComp(b, c, first);
                    addAndComp(b, c, second);
                    int r = 2;
                    while (true) {
                        if (addAndComp(b, c, first + second)) {
                            r++;
                            int t = first + second;
                            first = second;
                            second = t;
                        } else {
                            break;
                        }
                    }
                    res = Math.max(res, r);
                }
            }
        }
        out.println(res);
    }

    private boolean remove(HashMap<Integer, Integer> a, Integer i) {
        Integer c = a.get(i);
        if (c == null) return false;
        if (c > 1) {
            a.put(i, c - 1);
        } else {
            a.remove(i);
        }
        return true;
    }


    private boolean addAndComp(HashMap<Integer, Integer> b, HashMap<Integer, Integer> c, Integer i) {
        Integer cnt = c.get(i);
        if (cnt == null) {
            cnt = 1;
        } else {
            cnt++;
        }
        c.put(i, cnt);
        Integer cnt2 = b.get(i);
        if (cnt2 == null) {
            return false;
        }
        return cnt <= cnt2;
    }


    public static void main(String[] args) throws IOException {
        new Solution().run(args);
    }

    public void run(String[] args) throws IOException {
        if (args.length > 0 && "DEBUG_MODE".equals(args[0])) {
            in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
        }
        out = new PrintWriter(System.out);
//        out = new PrintWriter("output.txt");

//        int t = nextInt();
        int t = 1;
        for (int i = 0; i < t; i++) {
//            out.print("Case #" + (i + 1) + ": ");
            solve();
        }

        in.close();
        out.flush();
        out.close();
    }

    private int[] nextIntArray(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextInt();
        }
        return res;
    }

    private long[] nextLongArray(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextInt();
        }
        return res;
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private String nextToken() throws IOException {
        while (line == null || !line.hasMoreTokens()) {
            line = new StringTokenizer(in.readLine());
        }
        return line.nextToken();
    }

    private static class Pii {
        private int key;
        private int value;

        public Pii(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pii pii = (Pii) o;

            if (key != pii.key) return false;
            return value == pii.value;

        }

        @Override
        public int hashCode() {
            int result = key;
            result = 31 * result + value;
            return result;
        }
    }

    private static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair<?, ?> pair = (Pair<?, ?>) o;

            if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
            return !(value != null ? !value.equals(pair.value) : pair.value != null);

        }

        @Override
        public int hashCode() {
            int result = key != null ? key.hashCode() : 0;
            result = 31 * result + (value != null ? value.hashCode() : 0);
            return result;
        }
    }
}