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;
inline int IN() {
  int x = 0, ch = getchar(), f = 1;
  while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline void Out(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10)
    Out(x / 10), putchar(x % 10 + '0');
  else
    putchar(x + '0');
}
const int N = 1005;
int n, a[N], b[N], c[N], cnt;
int DFS(int x, int y) {
  int z = x + y, pos = lower_bound(b + 1, b + cnt + 1, z) - b;
  if (pos == cnt + 1 || b[pos] != z || !c[pos])
    return 0;
  else {
    c[pos]--;
    int ret = DFS(y, z) + 1;
    c[pos]++;
    return ret;
  }
}
int main() {
  n = IN();
  for (int i = 1; i <= n; i++) a[i] = IN();
  sort(a + 1, a + n + 1);
  b[1] = a[1], cnt = c[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] == a[i - 1])
      c[cnt]++;
    else
      b[++cnt] = a[i], c[cnt] = 1;
  }
  int Ans = 0;
  for (int i = 1; i <= cnt; i++)
    if (b[i] == 0) Ans = c[i];
  for (int i = 1; i <= cnt; i++)
    for (int j = 1; j <= cnt; j++) {
      if (b[i] == 0 && b[j] == 0) continue;
      if (i == j && c[i] < 2) continue;
      c[i]--, c[j]--;
      Ans = max(Ans, DFS(b[i], b[j]) + 2);
      c[i]++, c[j]++;
    }
  printf("%d\n", Ans);
}
