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.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class FibonacciIsh {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		int arr[] = new int[size];
		for (int i = 0; i < size; i++) {
			arr[i] = sc.nextInt();
		}
		getMaxFibIshCount(arr);
	}

	public static int getMaxFibIshCount(int[] arr) {
		Map<Integer, Integer> freq = new HashMap<>();
		Set<Double> set = new HashSet<>();
		for (int i : arr) {
			int c = freq.getOrDefault(i, 0);
			freq.put(i, ++c);
		}

		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (i != j) {
					int a = arr[i];
					int b = arr[j];
//					if (set.contains(a + 1d / b))
//						continue;
//					else
//						set.add(a + 1d / b);
					if (a == b && a == 0)
						max = Math.max(max, freq.get(0));
					else {
						int aFreq = freq.get(a);
						freq.put(a, --aFreq);
						int bFreq = freq.get(b);
						freq.put(b, --bFreq);
						int count = 2;
						while (true) {
							int c = a + b;
							int frq = freq.getOrDefault(c, 0);
							if (frq > 0) {
								freq.put(c, --frq);
								count++;
								a = b;
								b = c;
							} else {
								resetFreqMap(freq, count, a, b);
								break;
							}
						}
						max = Math.max(count, max);
					}
				}
			}
		}
		System.out.println(max);
		return max;
	}

	static void resetFreqMap(Map<Integer, Integer> frqMap, int count, int a, int b) {
		int f = frqMap.get(a);
		frqMap.replace(a, ++f);
		f = frqMap.get(b);
		frqMap.replace(b, ++f);
		while (count - 2 > 0) {
			int c = b - a;
			f = frqMap.get(c);
			frqMap.replace(c, ++f);
			b = a;
			a = c;
			count--;
		}
	}
}
