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.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long A[] = new long[n];
        Map<Long,Integer> isNextPresent = new HashMap<>();
        Set<Pair> isVisited = new HashSet<>();
        for(int i=0;i<n;i++) {
            A[i] = sc.nextLong();
            isNextPresent.put(A[i],isNextPresent.getOrDefault(A[i],0)+1);
        }
        int count = 0;
        for(int i=0;i<n;i++){
            int j=0;
            for(;j<n;j++){
                if(i==j)
                    continue;
                long num1 = A[i];
                long num2 = A[j];
                int curCount =2;
                if(num1==0&&num2==0){
                    curCount = isNextPresent.get(num1);
                    if(curCount>count)
                        count = curCount;
                    continue;
                }
                Pair p = new Pair(num1,num2);
                if(isVisited.contains(p))
                    continue;
                else
                    isVisited.add(p);
                isNextPresent.put(num1,isNextPresent.get(num1)-1);
                isNextPresent.put(num2,isNextPresent.get(num2)-1);
                while(true){
                    if(isNextPresent.getOrDefault(num1+num2,0)>0) {
                        long num3 = num1 + num2;
                        num1 = num2;
                        num2 = num3;
                        isNextPresent.put(num3,isNextPresent.get(num3)-1);
                        curCount++;
                    }else
                        break;;
                }
                if(curCount > count)
                    count = curCount;
                while (curCount > 0) {
                    isNextPresent.put(num2,isNextPresent.get(num2)+1);
                    long num3 = num2 -num1;
                    num2 = num1;
                    num1 = num3;
                    curCount--;
                }
            }
        }
        System.out.println(count);
    }
}
class Pair{
    public long n1,n2;
    public Pair(long n1, long n2){
        this.n1=n1;
        this.n2 =n2;
        }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return n1 == pair.n1 &&
                n2 == pair.n2;
    }

    @Override
    public int hashCode() {
        return Objects.hash(n1, n2);
    }
}