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;
const int N = 1005;
int a[N], vt[N], dem[N], num[N], tru[N];
int f[N][N];
int main() {
  int n;
  scanf("%d", &n);
  int dem0 = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    if (a[i] == 0) dem0++;
  }
  sort(a + 1, a + n + 1);
  vt[1] = 1;
  dem[vt[1]] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] != a[i - 1]) {
      vt[i] = i;
      dem[vt[i]] = 1;
    } else {
      vt[i] = vt[i - 1];
      dem[vt[i]]++;
    }
  }
  for (int i = 1; i <= n; i++) {
    int k = 1;
    for (int j = i + 1; j <= n; j++) {
      int tmp = a[i] + a[j];
      while (k <= n && (a[k] < tmp)) k++;
      if (k <= n && a[k] == tmp) {
        f[vt[i]][vt[j]] = f[vt[j]][vt[i]] = vt[k];
      }
    }
  }
  int ans = 0;
  if (dem0 >= 2) ans = dem0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (a[i] == 0 && a[j] == 0) continue;
      if (vt[i] == vt[j] && dem[vt[i]] < 2) continue;
      int cnt = 2;
      num[0] = vt[i];
      num[1] = vt[j];
      tru[num[0]]++;
      tru[num[1]]++;
      for (;; cnt++) {
        num[cnt] = f[num[cnt - 2]][num[cnt - 1]];
        if (num[cnt] == 0) break;
        if (dem[num[cnt]] == tru[num[cnt]]) break;
        tru[num[cnt]]++;
      }
      ans = max(ans, cnt);
      for (int k = 0; k < cnt; k++) tru[num[k]] = 0;
    }
  printf("%d", ans);
  return 0;
}
