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

public class P633D
{
	static int[] arr;
	public static void main(String[] args)
	{
		WozReader scan = new WozReader();
		int n = scan.nextInt();
		arr = new int[n];
		HashMap<Integer, Integer> map = new HashMap<>();
		int zeros = 0;
		for (int i = 0; i < n; i++)
		{
			arr[i] = scan.nextInt();
			if (arr[i] == 0)
				zeros++;
			add(map, arr[i]);
		}
		int longest = Math.max(2, zeros);
		HashSet<String> checked = new HashSet<>();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i == j)
					continue;
				if (arr[i] == 0 && arr[j] == 0)
					continue;
				if (checked.contains(arr[i]+""+arr[j]))
					continue;
				int len = 2;
				HashMap<Integer, Integer> used = new HashMap<>();
				add(used, arr[i]);
				add(used, arr[j]);
				int pp = arr[i];
				int p = arr[j];
				while (true)
				{
					int sum = p+pp;
					if (get(used, sum)+1 > get(map, sum))
						break;
					add(used, sum);
					pp = p;
					p = sum;
					len++;
				}
				longest = Math.max(longest, len);
				checked.add(arr[i] + "" + arr[j]);
			}
		}
		System.out.println(longest);
	}

	private static int get(HashMap<Integer, Integer> map, int n)
	{
		if (map.containsKey(n))
			return map.get(n);
		return 0;
	}

	private static void add(HashMap<Integer, Integer> map, int n)
	{
		if (map.containsKey(n))
			map.put(n, map.get(n)+1);
		else
			map.put(n, 1);
	}
	static class WozReader
	{
		BufferedReader br;
		StringTokenizer st;

		public WozReader()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
		}

		public String next()
		{
			if (st.hasMoreTokens())
				return st.nextToken();
			try
			{
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return st.nextToken();
		}

		public int nextInt()
		{
			return Integer.parseInt(next());
		}

		public long nextLong()
		{
			return Long.parseLong(next());
		}

		public String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}
