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.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;

public class D {

	private static int N;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		N = scanner.nextInt();
		HashMap<Integer, Integer> list = new HashMap<Integer, Integer>();
		int[] elements = new int[N];
		for(int i = 0; i < N; i++) {
			elements[i] = scanner.nextInt();
			list.put(elements[i], list.getOrDefault(elements[i], 0) + 1);
			
		}
		
		int max = 0;
		HashMap<String, Boolean> dp = new HashMap<String, Boolean>();
		StringBuilder key = new StringBuilder();
		
		//1) Pick two arbitrary starting elements
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {

				if(i == j) continue;

				// a then b
				int a = elements[i];
				int b = elements[j];

				// Check if such a configuration was already used (dp)
				key.setLength(0);
				key.append(a); key.append(' '); key.append(b);
				if(dp.containsKey(key.toString())) {
					continue;
				}
				dp.put(key.toString(), true);

				int value = getCount(a, b, list);
				max = Math.max(value, max);

			}

		}

		System.out.println(max);


	}

	private static int getCount(int a, int b, HashMap<Integer, Integer> list) {
		int count = 2;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(a, 1);
		map.put(b, map.getOrDefault(b, 0) + 1);
		
		for(int i = 3;;i++) {
			long nis = get(a, b, i);
			if(nis > (int) 1e10) break;
			int next = (int) nis;
			map.put(next, map.getOrDefault(next, 0));
			
			if(list.containsKey(next) && map.get(next) < list.get(next)) {
				map.put(next, map.get(next) + 1);
				count++;
				
			}
			else {
				break;
				
			}

		}
		
//		System.out.println("S");
//		for(Entry<Integer, Integer> e : map.entrySet()) {
//			System.out.println(e.getKey() + " " + e.getValue());
//		}
//		System.out.println("E: " + count);
		
		return count;

	}

	private static long[][] multiply(long[][] X, long[][] Y) {
		long[][] response = new long[2][2];
		response[0][0] = X[0][0]*Y[0][0] + X[0][1]*Y[1][0];
		response[0][1] = X[0][0]*Y[0][1] + X[0][1]*Y[1][1];
		response[1][0] = X[1][0]*Y[0][0] + X[1][1]*Y[1][0];
		response[1][1] = X[1][0]*Y[0][1] + X[1][1]*Y[1][1];
		return response;
	}

	private static long[][] power(long[][] X, int N) {
		if(N == 1) {
			return X;
		} 
		else if(N % 2 == 1) {
			return multiply(X, power(X,N - 1));

		}
		else {
			long[][] X2 = power(X, N/2);
			return multiply(X2,X2);
		}

	}

	private static long get(int a, int b, int n) {

		if(n == 1) return a;
		if(n == 2) return b;

		long[][] X = new long[][] {{0,1},{1,1}};
		long[][] matrix = power(X, n - 1);

		return matrix[0][0] * a + matrix[0][1] * b;

	}


}
