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.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Fib {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int[] arr = new int[n];
		for (int a = 0; a < n; a++) {
			arr[a] = input.nextInt();
		}

		HashMap<Integer, Integer> freqDist = new HashMap<Integer, Integer>();
		for (int a = 0; a < n; a++) {
			add(arr[a], freqDist);
		}
		int max = 0;
		HashSet<Long> cache = new HashSet<Long>();
		for (int start = 0; start < n; start++) {
			for (int end = 0; end < n; end++) {
				if (start != end) {
					if(cache.contains(arr[start]*2000000000l+arr[end])){
						continue;
					}
					cache.add(arr[start]*2000000000l+arr[end]);
					ArrayList<Integer> storage = new ArrayList<Integer>();

					int count = 2;
					int s = arr[start];
					int e = arr[end];
					storage.add(arr[start]);
					storage.add(arr[end]);
					remove(arr[start], freqDist);
					remove(arr[end], freqDist);
					while (true) {
						int asdf = s + e;
						s = e;
						e = asdf;
						if (freqDist.containsKey(asdf) && freqDist.get(asdf) > 0) {
							storage.add(asdf);
							remove(asdf, freqDist);
						}
						else{
							break;
						}
						count++;
					}
					max = Math.max(count, max);
					for(int i:storage){
						add(i, freqDist);
					}
				}
			}
		}
		System.out.println(max);

	}

	public static void add(int i, HashMap<Integer, Integer> map) {
		if (!map.containsKey(i)) {
			map.put(i, 0);
		}
		map.put(i, map.get(i) + 1);
	}

	public static void remove(int i, HashMap<Integer, Integer> map) {
		if (!map.containsKey(i)) {
			map.put(i, 0);
		}
		map.put(i, map.get(i) - 1);
	}
}
