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 double EPS = 1e-8;
const long long SZ = 1010, SSZ = 21, APB = 26, one = 93,
                INF = 0x3fffffffffffffff, mod = 1000000007;
const int intINF = 0x3f3f3f3f;
double PI = acos(-1);
long long n, arr[SZ];
int tim;
multiset<long long> src, cur;
set<pair<long long, long long> > vst;
void init() {
  cin >> n;
  for (long long i = 1; i <= n; ++i) cin >> arr[i], src.insert(arr[i]);
  long long res = 0;
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 1; j <= n; ++j) {
      if (!(arr[i] == 0 && arr[j] == 0) && i != j &&
          vst.find(make_pair(arr[i], arr[j])) == vst.end()) {
        vst.insert(make_pair(arr[i], arr[j]));
        cur.clear();
        cur.insert(arr[i]);
        cur.insert(arr[j]);
        src.erase(src.find(arr[i]));
        src.erase(src.find(arr[j]));
        long long num = 2, a1 = arr[i], a2 = arr[j];
        for (int k = 0; k < 90; ++k) {
          long long a3 = a1 + a2;
          if (src.find(a3) == src.end()) break;
          cur.insert(a3);
          src.erase(src.find(a3));
          ++num;
          a1 = a2, a2 = a3;
        }
        for (auto it = cur.begin(); it != cur.end(); ++it) {
          src.insert(*it);
        }
        res = max(res, num);
      }
    }
  }
  res = max(res, (long long)count(arr + 1, arr + 1 + n, 0));
  cout << res << endl;
}
void work() {}
int main() {
  std::ios::sync_with_stdio(0);
  long long casenum;
  {
    init();
    work();
  }
  return 0;
}
