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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class D {
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int N = Integer.parseInt(br.readLine());
		
		
		StringTokenizer tokenizer = new StringTokenizer(br.readLine());
		
		long [] a = new long[N];
		
		HashMap<Long, Integer> map = new HashMap<Long, Integer>();
		
		
		for(int i=0; i<N; i++) { 
			a[i] = Long.parseLong(tokenizer.nextToken());
			
			Integer val = map.get(a[i]);
			
			if(null == val) val = 0;
			++val;
			
			map.put(a[i], val);
			
		}
		int sol = 2;
		
		
		boolean zeroZero = false;
		for(int i=0; i<N; ++i) { 
			for(int j=0; j<N; ++j) { 
				
				if(i == j) continue;
				
				
				if(zeroZero && a[i] == a[j] && a[j] == 0) { 
					continue;
				}
				
				if(a[i] == a[j] && a[i] == 0) {
					zeroZero = true;
				}
				int counter = 2;
				
				long lastPlayer = a[i];
				long currVal = a[i] + a[j];
				
				HashMap<Long, Integer> currMap = new HashMap<Long, Integer>();
				
				currMap.put(a[i], 1);
				
				if(a[i] == a[j])
					currMap.put(a[j],2);
				else
					currMap.put(a[j], 1);
				
				while(true) { 
					
					Integer numTimes = map.get(currVal);

					if(null == numTimes) {
						break;
					}
					
					Integer currNumTimes = currMap.get(currVal);
					
					if(null == currNumTimes) 
						currNumTimes = 0;
					
					//System.out.println("currNumTimes: " + currNumTimes + " numTimes: " + numTimes);
					
					if(currNumTimes >= numTimes) break;
					
					currMap.put(currVal, 1 + currNumTimes);
					
					long temp = currVal;
					currVal+= lastPlayer;
					
					lastPlayer = temp;
					++counter;
				}
				//System.out.println("counter: " + counter);
				sol = Math.max(counter, sol);
				
				
			
			}
		}
		
		System.out.println(sol);
		
	}
}