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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Set;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ATailouloute
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        QuickScanner in = new QuickScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Fibonacci solver = new Fibonacci();
        solver.solve(1, in, out);
        out.close();
    }

    static class Fibonacci {
        int n;

        public void solve(int testNumber, QuickScanner in, PrintWriter out) {
            n = in.nextInt();
            int[] a = in.nextIntArray(n);
            int ans = (int) Arrays.stream(a).filter(x -> x == 0).count();
            Counter<Integer> cnt = new Counter<>();
            for (int x : a) cnt.increment(x);
            Set<IntPair> done = new HashSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    if (done.contains(new IntPair(a[i], a[j]))) continue;
                    done.add(new IntPair(a[i], a[j]));
                    Counter<Integer> cur = new Counter<>();
                    int left = a[i], right = a[j];
                    cur.increment(left);
                    cur.increment(right);
                    int curAns = 2;
                    for (; ; ) {
                        if (cnt.count(left + right) - cur.count(left + right) > 0) {
                            cur.increment(left + right);
                            int tmp = left + right;
                            left = right;
                            right = tmp;
                            curAns++;
                        } else break;
                    }
                    ans = Math.max(ans, curAns);
                }
            }
            out.println(ans);
        }

    }

    static class Counter<T> {
        Map<T, Integer> data;
        int total;

        public Counter() {
            this.data = new HashMap<>();
        }

        public int count(T key) {
            return data.containsKey(key) ? data.get(key) : 0;
        }

        public void add(T key, int value) {
            set(key, count(key) + value);
            total += value;
        }

        public void increment(T key) {
            add(key, 1);
        }

        public void set(T key, int value) {
            data.put(key, value);
        }

    }

    static class QuickScanner {
        BufferedReader br;
        StringTokenizer st;
        InputStream is;

        public QuickScanner(InputStream stream) {
            is = stream;
            br = new BufferedReader(new InputStreamReader(stream), 32768);
        }

        public String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public int[] nextIntArray(int len) {
            int[] a = new int[len];
            for (int i = 0; i < len; i++) {
                a[i] = nextInt();
            }
            return a;
        }

    }

    static class IntPair implements Comparable<IntPair> {
        final int first;
        final int second;

        public IntPair() {
            this(0, 0);
        }

        public IntPair(int u, int v) {
            this.first = u;
            this.second = v;
        }


        public int hashCode() {
            int hu = (int) (first ^ (first >>> 32));
            int hv = (int) (second ^ (second >>> 32));
            return 31 * hu + hv;
        }


        public boolean equals(Object obj) {
            IntPair pair = (IntPair) obj;
            return pair.first == first && pair.second == second;
        }


        public int compareTo(IntPair o) {
            return first == o.first ? Integer.compare(second, o.second) : Integer.compare(first, o.first);
        }


        public String toString() {
            return String.format("(%d,%d)", first, second);
        }

    }
}

