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.
#include <bits/stdc++.h>
using namespace std;
long long aaa[10000 + 10];
long long c[1000 + 10];
long long cnt;
long long n;
int main() {
  scanf("%I64d", &n);
  long long summ = 0;
  for (long long i = 1; i <= n; i++) {
    scanf("%I64d", &aaa[i]);
    if (aaa[i] == 0) summ += 1;
  }
  sort(aaa + 1, aaa + (n + 1));
  long long max = 0;
  for (long long i = 1; i <= n; i++) {
    for (long long q = 1; q <= n; q++) {
      if (i == q || aaa[i] == 0 && aaa[q] == 0) continue;
      memset(c, 0, sizeof(c));
      c[lower_bound(aaa + 1, aaa + (n + 1), aaa[i]) - (aaa)] += 1;
      c[lower_bound(aaa + 1, aaa + (n + 1), aaa[q]) - (aaa)] += 1;
      int sum = 2;
      long long aa = aaa[i];
      long long bb = aaa[q];
      for (;;) {
        long long a1 = upper_bound(aaa + 1, aaa + (n + 1), aa + bb) - (aaa);
        long long a2 = lower_bound(aaa + 1, aaa + (n + 1), aa + bb) - (aaa);
        if (aaa[a2] != aa + bb || c[a2] >= a1 - a2) break;
        c[a2] += 1;
        long long cc = aa;
        aa = bb, bb += cc;
        sum += 1;
      }
      if (sum > max) max = sum;
    }
  }
  if (summ > max) max = summ;
  printf("%I64d\n", max);
}
