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.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Vector;

public class D {
    
    class Pair {
        int a, b;
        
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
        
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Pair))
                return false;
        
            Pair p = (Pair)o;
            return a == p.a && b == p.b;
        }
        
        @Override
        public int hashCode() {
            return a * 10003 + b;
        }
    }
    
    public static final boolean DEBUG = false;
    String filename = "";
    Scanner sc;
    PrintWriter pw;

    public void debug(Object o) {
        if (DEBUG) {
            int ln = Thread.currentThread().getStackTrace()[2].getLineNumber();
            String fn = Thread.currentThread().getStackTrace()[2].getFileName();
            System.out.println("(" + fn + ":" + ln + "): " + o);
        }
    }

    public void pln(Object o) {
        System.out.println(o);
    }

    int n;
    HashMap<Integer, Integer> h;
    HashSet<Pair> set = new HashSet<Pair>();
    int[] v;
    Vector<Integer> sol = new Vector<Integer>();
    int simulate(int a, int b) {
        Pair pair = new Pair(a, b);
        if (set.contains(pair)) {
            return 0;
        }
        set.add(pair);
        
        if (!h.containsKey(a + b)) {
            return 2;
        }
        
        sol.clear();
        sol.add(a); sol.add(b);
        h.put(a, h.get(a) - 1);
        h.put(b, h.get(b) - 1);
        
        int crt = 2;
        while (true) {
            int c = a + b;
            Integer nr = h.get(c);
            if (nr != null && nr != 0) {
                crt++;
                a = b;
                b = c;
                h.put(c, nr - 1);
                sol.add(c);
            } else {
                break;
            }
        }
        
        for (int val: sol) {
            h.put(val, h.get(val) + 1);
        }
        
        return crt;
    }
    
    public void solve() {

        n = sc.nextInt();
        h = new HashMap<Integer, Integer>();
        v = new int[n];
        int numZeros = 0;
        
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            Integer n = h.get(v[i]);
            if (n == null) n = 0;
            h.put(v[i], n + 1);
            if (v[i] == 0) numZeros++;
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                if ((v[i] > 0 && v[j] > 0)
                        || (v[i] < 0 && v[j] < 0)) {
                    if (h.containsKey(v[j] - v[i])) {
                        continue;
                    }
                }
                
                if (v[i] == 0 && v[j] == 0) {
                    if (numZeros > result) {
                        result = numZeros;
                    }
                    continue;
                }
                
                int crt = simulate(v[i], v[j]);
                if (crt > result) {
                    result = crt;
                }
            }
        }
        
        pw.println(result);
    }
    
    public void run() throws FileNotFoundException {
        if (filename.isEmpty()) {
            sc = new Scanner(System.in);
            pw = new PrintWriter(System.out);
        } else {
            sc = new Scanner(new File(filename + ".in"));
            pw = new PrintWriter(new File(filename + ".out"));
        }
        
        solve();
        
        pw.close();
        sc.close();
    }

    public static void main(String[] args) {
        D t = new D();
        try {
            t.run();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}