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 MAXN = (1 << 10);
int n, k = 0, last, f, s;
long long a[MAXN];
void read() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
}
map<long long, int> pos;
int nxt[MAXN][MAXN];
int cnt[MAXN], id[MAXN];
int c[MAXN];
void solve() {
  sort(a, a + n);
  for (int i = 0; i < n; i++) pos[a[i]] = i + 1;
  id[0] = 0;
  for (int i = 1; i < n; i++)
    if (a[i] != a[i - 1])
      id[i] = id[i - 1] + 1;
    else
      id[i] = id[i - 1];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      nxt[id[i]][id[j]] =
          (pos[a[i] + a[j]] >= 1) ? id[pos[a[i] + a[j]] - 1] : (-1);
  for (int i = 0; i < n; i++) cnt[id[i]]++;
  int ans = 1;
  for (int i = 0; i <= id[n - 1]; i++)
    for (int j = 0; j <= id[n - 1]; j++)
      if (i != j || cnt[i] >= 2) {
        f = i;
        s = j;
        c[f]++;
        c[s]++;
        for (k = 2; k <= n; k++)
          if (nxt[f][s] != -1 && c[nxt[f][s]] < cnt[nxt[f][s]]) {
            last = f;
            f = s;
            s = nxt[last][s];
            c[s]++;
          } else
            break;
        k = min(k, n);
        if (ans < k) ans = k;
        f = i;
        s = j;
        c[f]--;
        c[s]--;
        for (k = 2; k <= n; k++)
          if (nxt[f][s] != -1 && c[nxt[f][s]]) {
            last = f;
            f = s;
            s = nxt[last][s];
            c[s]--;
          } else
            break;
      }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}
