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;
int N, M, x, foo;
int a[10005];
int res = 2;
multiset<int> pos;
int cntZero = 0;
set<pair<int, int> > used;
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", a + i);
    if (a[i] == 0) cntZero++;
  }
  for (int i = 0; i < N; i++) {
    pos.insert(a[i]);
  }
  vector<int> toAdd;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int temp = 2;
      if (i == j) continue;
      if (used.find(make_pair(a[i], a[j])) != used.end()) continue;
      used.insert(make_pair(a[i], a[j]));
      if (a[i] == 0 && a[j] == 0) {
        res = max(res, cntZero);
        continue;
      }
      int last = a[j];
      int prevLast = a[i];
      if (last >= 1e9 + 1 && prevLast >= 1e9 + 1) {
        continue;
      }
      if (last < -1e9 && prevLast < -1e9) {
        continue;
      }
      int sum = a[i] + a[j];
      toAdd.push_back(a[i]);
      toAdd.push_back(a[j]);
      pos.erase(pos.find(a[i]));
      pos.erase(pos.find(a[j]));
      while (pos.find(sum) != pos.end()) {
        pos.erase(pos.find(sum));
        toAdd.push_back(sum);
        temp++;
        swap(last, prevLast);
        last = sum;
        if (last >= 1e9 + 1 && prevLast >= 1e9 + 1) {
          break;
        }
        if (last < -1e9 && prevLast < -1e9) {
          break;
        }
        sum = last + prevLast;
      }
      for (int x = 0; x < toAdd.size(); x++) {
        pos.insert(toAdd[x]);
      }
      toAdd.clear();
      res = max(res, temp);
    }
  }
  printf("%d\n", res);
}
