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 big = 1000000007ll;
long long n, m, k, q;
long long T;
std::vector<long long> A;
std::set<long long> S;
std::map<long long, long long> M;
std::vector<long long> ANS;
int main() {
  long long c1, c2, c3, c4, c5;
  long long x, y, z;
  long long a, b, c, d, e, f;
  std::cin >> n;
  long long a1, a2;
  long long ma = 0;
  long long n2 = 0;
  for (c1 = 0; c1 < n; c1++) {
    std::cin >> a;
    if (S.find(a) == S.end()) {
      M[a] = 1;
      S.insert(a);
    } else {
      M[a]++;
    }
    if (M[a] <= 2) {
      n2++;
      A.push_back(a);
    }
    ANS.push_back(0);
  }
  for (c1 = 0; c1 < n2; c1++) {
    for (c2 = 0; c2 < n2; c2++) {
      if (c1 != c2) {
        a = A[c1];
        b = A[c2];
        long long matemp = 2;
        std::map<long long, long long> M2;
        std::set<long long> S2;
        S2.clear();
        M2.clear();
        M2[a + b] = 1;
        S2.insert(a + b);
        if (S2.find(a) != S2.end()) {
          M2[a]++;
        } else {
          M2[a] = 1;
          S2.insert(a);
        }
        if (S2.find(b) != S2.end()) {
          M2[b]++;
        } else {
          M2[b] = 1;
          S2.insert(b);
        }
        while (S.find(a + b) != S.end()) {
          if (M[a + b] >= M2[a + b]) {
            c = b;
            b = a + b;
            a = c;
            if (S2.find(a + b) != S2.end()) {
              M2[a + b]++;
            } else {
              M2[a + b] = 1;
              S2.insert(a + b);
            }
            matemp++;
          } else {
            break;
          }
        }
        if (matemp > ma) {
          ma = matemp;
          a1 = c1;
          a2 = c2;
        }
      }
    }
  }
  std::cout << ma << "\n";
  return 0;
}
