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 int n, a[2005];
map<pair<long long int, long long int>, long long int> dp;
map<long long int, long long int> pres;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<long long int> pos, neg;
  long long int ct = 0;
  for (long long int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (a[i] >= 0)
      pos.push_back(a[i]);
    else
      neg.push_back(a[i]);
    if (a[i] == 0) ct++;
    pres[a[i]]++;
  }
  if (ct > 1) dp.insert(make_pair(make_pair(0LL, 0LL), ct));
  sort(pos.begin(), pos.end());
  for (long long int i = ((long long int)pos.size()) - 1; i >= 0; i--) {
    for (long long int j = ((long long int)pos.size()) - 1; j >= i + 1; j--) {
      long long int v1 = pos[i], v2 = pos[j];
      if (dp.find(make_pair(v1, v2)) != dp.end()) continue;
      dp.insert(make_pair(make_pair(v1, v2), 2LL));
      if (dp.find(make_pair(v2, v1 + v2)) != dp.end())
        dp[make_pair(v1, v2)] = max(2LL, 1 + dp[make_pair(v2, v1 + v2)]);
    }
  }
  sort(neg.begin(), neg.end());
  reverse(neg.begin(), neg.end());
  for (long long int i = ((long long int)neg.size()) - 1; i >= 0; i--) {
    for (long long int j = ((long long int)neg.size()) - 1; j >= i + 1; j--) {
      long long int v1 = neg[i], v2 = neg[j];
      if (dp.find(make_pair(v1, v2)) != dp.end()) continue;
      dp.insert(make_pair(make_pair(v1, v2), 2LL));
      if (dp.find(make_pair(v2, v1 + v2)) != dp.end())
        dp[make_pair(v1, v2)] = max(2LL, 1 + dp[make_pair(v2, v1 + v2)]);
    }
  }
  for (long long int i = 1; i <= n; ++i)
    for (long long int j = 1; j <= n; ++j) {
      if (j == i) continue;
      long long int v1 = a[i], v2 = a[j];
      if (dp.find(make_pair(v1, v2)) != dp.end()) continue;
      map<long long int, long long int> req;
      long long int ans = 0, ctr = 0;
      while (1) {
        if (v1 >= 0 && v2 >= v1 && v1 > abs(a[i]) && v1 > abs(a[j])) {
          ans += max(1LL, dp[make_pair(v1, v2)]);
          break;
        }
        if (v1 < 0 && v2 < v1 && v1 < -1 * abs(a[i]) && v1 < -1 * abs(a[j])) {
          ans += max(1LL, dp[make_pair(v1, v2)]);
          break;
        }
        if (!ctr) req[v1]++;
        req[v2]++;
        ctr = 1;
        if (req[v1] > pres[v1] || req[v2] > pres[v2]) {
          ans++;
          break;
        }
        ans++;
        long long int tem = v1 + v2;
        v1 = v2;
        v2 = tem;
      }
      dp[make_pair(a[i], a[j])] = ans;
    }
  long long int ans = 2;
  for (auto& xp : dp) ans = max(ans, xp.second);
  cout << ans << endl;
}
