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 q3 {
	public static void main(String[] args) throws Exception
	{
		InputReader in=new InputReader(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=in.nextInt();
		int count=0;
		long[] a=new long[n];
		HashMap<Long,Integer> hm=new HashMap<Long,Integer>();
		for(int i=0;i<n;i++)
		{
			a[i]=in.nextLong();
			if(a[i]==0 )
			{
				count++;
			}
			if(hm.containsKey(a[i]))
			{
				int cc=hm.get(a[i]);
				hm.put(a[i],cc+1);
			}
			else
			{
				hm.put(a[i],1);
			}
		}
		int maxsize=2;
		HashSet<LongLongPair> hs=new HashSet<LongLongPair>();
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				LongLongPair aa=new LongLongPair(a[i],a[j]);
				
				if(hs.contains(aa))
				{
					continue;
				}
				else
				{
					hs.add(aa);
				}
				if(a[i]==0 && a[j]==0)
				{
					continue;
				}
				int size=2;
				ArrayList<Long> ar=new ArrayList<Long>();
				int mm1=hm.get(a[i]);
				mm1--;
				if(mm1==0)
				{
					hm.remove(a[i]);
				}
				else
				{
					hm.put(a[i], mm1);
				}
				mm1=hm.get(a[j]);
				mm1--;
				if(mm1==0)
				{
					hm.remove(a[j]);
				}
				else
				{
					hm.put(a[j], mm1);
				}
				ar.add(a[i]);
				ar.add(a[j]);
				//HashMap<Long,Integer> temp=(HashMap<Long,Integer>)hm.clone();
				long prv=a[j];
				long cur=a[i]+a[j];
				while(hm.containsKey(cur))
				{
					ar.add(cur);
					size++;
					int cm=hm.get(cur);
					cm--;
					if(cm==0)
					{
						hm.remove(cur);
					}
					else
					{
						hm.put(cur, cm);
					}
					long mm=cur+prv;
					prv=cur;
					cur=mm;
					
				}
				maxsize=Math.max(maxsize, size);
				for(int f=0;f<ar.size();f++)
				{
					long kk=ar.get(f);
					if(hm.containsKey(kk))
					{
						int cc=hm.get(kk);
						hm.put(kk, cc+1);
					}
					else
					{
						hm.put(kk, 1);
					}
				}
			}
		}
		//int maxsize=2;
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				LongLongPair aa=new LongLongPair(a[j],a[i]);

				if(hs.contains(aa))
				{
					continue;
				}
				else
				{
					hs.add(aa);
				}
				if(a[i]==0 && a[j]==0)
				{
					continue;
				}
				int size=2;
				//HashMap<Long,Integer> temp=hm;
				ArrayList<Long> ar=new ArrayList<Long>();
				int mm1=hm.get(a[i]);
				mm1--;
				if(mm1==0)
				{
					hm.remove(a[i]);
				}
				else
				{
					hm.put(a[i], mm1);
				}
				mm1=hm.get(a[j]);
				mm1--;
				if(mm1==0)
				{
					hm.remove(a[j]);
				}
				else
				{
					hm.put(a[j], mm1);
				}
				long prv=a[i];
				long cur=a[i]+a[j];
				ar.add(a[i]);
				ar.add(a[j]);
				while(hm.containsKey(cur))
				{
					ar.add(cur);
					size++;
					int cm=hm.get(cur);
					cm--;
					if(cm==0)
					{
						hm.remove(cur);
					}
					else
					{
						hm.put(cur, cm);
					}
					long mm=cur+prv;
					prv=cur;
					cur=mm;
					
				}
				maxsize=Math.max(maxsize, size);
				for(int f=0;f<ar.size();f++)
				{
					long kk=ar.get(f);
					if(hm.containsKey(kk))
					{
						int cc=hm.get(kk);
						hm.put(kk, cc+1);
					}
					else
					{
						hm.put(kk, 1);
					}
				}
			}
		}
		pw.println(Math.max(maxsize,count));
		pw.close();
	}
	
	
	
	
	
	
	
	
	 static class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar;
		private int snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}

			int res = 0;

			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}

			long res = 0;

			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));

			return res * sgn;
		}
		
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

}
 class LongLongPair implements Comparable<LongLongPair> {
    public final long first;
    public final long second;

    public LongLongPair(long first, long second) {
        this.first = first;
        this.second = second;
    }


    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        LongLongPair pair = (LongLongPair) o;

        return first == pair.first && second == pair.second;
    }


    public int hashCode() {
        int result = Long.hashCode(first);
        result = 31 * result + Long.hashCode(second);
        return result;
    }


    public String toString() {
        return "(" + first + "," + second + ")";
    }

    @SuppressWarnings({"unchecked"})
    public int compareTo(LongLongPair o) {
        int value = Long.compare(first, o.first);
        if (value != 0) {
            return value;
        }
        return Long.compare(second, o.second);
    }

}

