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.HashMap;
import java.util.StringTokenizer;

public class S1 {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

	void solve() throws IOException {
        int t = 1;
        while (t-- > 0) {
            solveTest();
        }
	}

    void solveTest() throws IOException {
        int n = readInt();
        int[] a = readArr(n);
        HashMap<Integer, Integer> count = new HashMap<>();
        int zeroCount = 0;
        for(int i = 0; i < n; i++) {
            if(!count.containsKey(a[i])) {
                count.put(a[i], 0);
            }
            count.put(a[i], count.get(a[i]) + 1);
            if(a[i] == 0) {
                zeroCount++;
            }
        }
        int res = zeroCount;
        for(int first: count.keySet()) {
            for(int second: count.keySet()) {
                HashMap<Integer, Integer> cur = new HashMap<>();
                if(first == second && count.get(first) == 1) continue;
                int curRes = 2;
                int x = second;
                int y = first;
                if(x == y) {
                    cur.put(x, 2);
                } else {
                    cur.put(x, 1);
                    cur.put(y, 1);
                }
                while (true) {
                    int next = x + y;
                    Integer cntn = count.get(next);
                    if(cntn == null) break;
                    Integer cn = cur.get(next);
                    if(cn == null) cn = 0;
                    if(cn < cntn) {
                        curRes++;
                        y = x;
                        x = next;
                        cur.put(next, cn+1);
                    } else {
                        break;
                    }
                }
                if(curRes > res) {
                    res = curRes;
                }
            }
        }
        out.println(res);
    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

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

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

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

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }
}