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.*;
import java.util.*;
public class d {
public static void main(String[] args) throws IOException {
	input.init(System.in);
	PrintWriter out = new PrintWriter(System.out);
	int n = input.nextInt();
	int[] as = new int[n];
	long oo = (long)2e9+7;
	for(int i = 0; i<n; i++) as[i] = input.nextInt();
	HashSet<Long> used = new HashSet<Long>();
	HashMap<Integer, Integer> fs = new HashMap<Integer, Integer>();
	HashMap<Integer, Integer> seq = new HashMap<Integer, Integer>();
	for(int i = 0; i<n; i++)
	{
		fs.put(as[i], fs.containsKey(as[i]) ? (1+fs.get(as[i])) : 1);
		seq.put(as[i], 0);
	}
	int res = 0;
	for(int i = 0; i<n; i++)
		for(int j = 0; j<n; j++)
		{
			if(i == j) continue;
			long key = as[i]*oo + as[j];
			if(used.contains(key)) continue;
			used.add(key);
			int cur = 2;
			seq.put(as[i], 1);
			seq.put(as[j], as[i] == as[j] ? 2 : 1);
			ArrayList<Integer> list = new ArrayList<Integer>();
			list.add(as[i]);
			list.add(as[j]);
			int a = as[i], b = as[j];
			while(true)
			{
				//System.out.println(a+" "+b);
				key = a*oo+b;
				used.add(key);
				if(Math.abs(a+b) > 1e9) break;
				int next = a+b;
				if(fs.containsKey(next) && fs.get(next) > seq.get(next))
				{
					list.add(next);
					seq.put(next, seq.get(next)+1);
					cur++;
					a = b;
					b = next;
				}
				else break;
			}
			for(int x : list) seq.put(x, 0);
			res = Math.max(res, cur);
		}
	out.println(res);
	out.close();
}

public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}

