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.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.io.*;
import java.util.*;

public class ManthanD
{

private static StringTokenizer st;
    
    public static void nextLine(BufferedReader br) throws IOException
    {
        st = new StringTokenizer(br.readLine());
    }
    
    public static int nextInt()
    {
        return Integer.parseInt(st.nextToken());
    }
    
    public static String next()
    {
        return st.nextToken();
    }
    
    public static long nextLong()
    {
        return Long.parseLong(st.nextToken());
    }

    public static double nextDouble()
    {
        return Double.parseDouble(st.nextToken());
    }
    
    static long[] a;
    static HashMap<Long, Integer> map;
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nextLine(br);
        int n = nextInt();
        nextLine(br);
        a = new long[n];
        map = new HashMap<Long, Integer>();
        int zeros = 0;
        for (int i = 0; i < n; i++)
        {
            a[i] = nextLong();
            if (!map.containsKey(a[i]))
            {
                map.put(a[i], 1);
            }
            else
            {
                map.put(a[i], map.get(a[i]) + 1);
            }
            if (a[i] == 0)
            {
                zeros++;
            }
        }
        int best = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (a[i] == 0 && a[j] == 0)
                {
                    best = Math.max(best, zeros);
                    continue;
                }
                best = Math.max(best, test(a[i], a[j]));
                best = Math.max(best, test(a[j], a[i]));
            }
        }
        System.out.println(best);
    }
    
    static int test(long a, long b)
    {
        long c = a + b;
        int ans = 2;
        HashMap<Long, Integer> map2 = new HashMap<Long, Integer>();
        map2.put(a, 1);
        if (a != b)
        {
            map2.put(b, 1);
        }
        else
        {
            map2.put(a, 2);
        }
        while (Math.abs(c) < 1000000001)
        {
            Integer count = map.get(c);
            if (count == null)
            {
                break;
            }
            Integer count2 = map2.get(c);
            if (count2 == null)
            {
                map2.put(c, 1);
            }
            else
            {
                if (count2 >= count)
                {
                    break;
                }
                map2.put(c, count2 + 1);
            }
            long d = b + c;
            b = c;
            c = d;
            ans++;
        }
        return ans;
    }
}