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.util.*;
import javafx.util.Pair;
public class Fibonaccish {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
       Scanner s=new Scanner(System.in);
       int n=s.nextInt();
       int[] arr=new int[n];
       int temp=0;
       int ans=0;
       
       Map<Integer, Integer> freq=new HashMap<>();
       Map<Pair, Boolean> check=new HashMap<>();
       
       for(int i=0; i<n; i++)
    	   {
    	   arr[i]=s.nextInt();
    	   freq.put(arr[i], freq.getOrDefault(arr[i], 0)+1);
    	   }
       
       for(int  i=0; i<n; i++) {
    	   
    	  
    	   for(int j=0; j<n; j++)                //starting from 0 as fibonacii with (i,j) amd (j,i) are not same in all cases
    	   {
    		     if(i == j)
    			   continue;
    		   
    			  int f=arr[i];
    			  int sc=arr[j];
    			  
    			  Pair<Integer, Integer> p=new Pair<>(f,sc);
    			  if(check.containsKey(p)==true)
    				  continue;
    			  
    			  check.put(p, true);
    			  if(f==0 && sc==0) {
    				  ans=Math.max(ans, freq.get(0));
    				  continue;
    			  }
    			  
    			  freq.put(f, freq.get(f)-1);
    			  freq.put(sc, freq.get(sc)-1);
    			  
    			  int count=0;
    			  int prev=0;
    			  while(freq.containsKey(f+sc) && freq.get(f+sc)>0) {
    				  count++;
    				  freq.put(f+sc, freq.get(f+sc)-1);
    				    
        			  temp=f+sc;
        			     
        			  f=sc;
        			  sc=temp;
    			  }
    			//  prev=sc;  //for backtracking
    			  ans=Math.max(ans, count+2);
    			  
    			  freq.put(f, freq.get(f)+1);
    			  
    			
    				  freq.put(sc, freq.get(sc)+1);
    				//  continue;
    			  
    			//  freq.put(prev, freq.get(prev)+1);
    			  
    			  while(count!=0) {
    				  
    				  temp=sc-f;
    				  //System.out.println(f+" "+prev);
    				  freq.put(temp, freq.get(temp)+1);
    				  count--;
    				  
    				  sc=f;
    				  f=temp;
    				  
    			  }
    		   
    	   }
       }
       System.out.println(ans);
	}

}
