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.*;
public class Fibonacciish {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] arr = new int[n];
		Map<Integer,Integer> hmap = new HashMap();
		Map<String,Integer> dp = new HashMap();
		for(int i=0; i<n;i++) {
			arr[i]=in.nextInt();
			hmap.put(arr[i], hmap.getOrDefault(arr[i], 0)+1);
		}
		Arrays.sort(arr);
		int max=0;
		for(int i = 0; i < n; i++) {  
	        for(int j = 0; j < n; j++) {  
	            if(i == j) 
	            		continue; 
	            if(arr[i]==0&&arr[j]==0)
                {
                    max=Math.max(max,hmap.get(0));
                    continue;
                }
	            hmap.put(arr[i], hmap.get(arr[i])-1);
	            hmap.put(arr[j], hmap.get(arr[j])-1);
	            max = Math.max(max, CountCall(arr[i], arr[j],hmap,dp) + 2);  
	            hmap.put(arr[i], hmap.get(arr[i])+1);
	            hmap.put(arr[j], hmap.get(arr[j])+1); 
	        }  
	    } 
		System.out.println(max);
	}
	static int CountCall(int a, int b, Map<Integer, Integer> hmap, Map<String, Integer> dp) {
		 if(dp.containsKey(a+" "+b))
	    		return dp.get(a+" "+b);
		 dp.put(a+" " + b, Count(a, b, hmap));
		 return dp.get(a + " " + b);
		 
		 
	}
	
	static int Count(int a, int b,Map<Integer,Integer> hmap) {  
	    int max = 0;  
	   
	    if(hmap.containsKey(a+b) && hmap.get(a+b)>0)  
	    {  
	        hmap.put(a+b, hmap.get(a+b)-1);
	        max = Count(b, a+b,hmap) + 1;  
	        hmap.put(a+b, hmap.get(a+b)+1);
	    }  
	    
	    return max;  
	}  
}
