Giải bài trực tuyến

Cho dãy A gồm N số nguyên. Một dãy con của dãy A là dãy gồm các phần tử A[i1], A[i2], ..., A[iM] thỏa mãn : 1 <= i1 < i2 < ... < iM <= N. Hãy tìm dãy con B dài nhất thỏa mãn điều kiện: B[i] = B[i-1] + B[i-2] với i >= 3

Input

• Dòng 1: T - số test (1 <= T <= 15).
• Tiếp theo là 2T dòng mô tả các test, mỗi test gồm:
  • Dòng 1: N (3 <= N <= 2500)
  • Dòng 2: N số A[1], A[2], ..., A[N]. Các số có giá trị tuyệt đối không quá 10^6

Output

Gồm T dòng, mỗi dòng ghi 1 số nguyên là độ dài dãy con dài nhất.

Example

Input:
1
7
-20 87 20 0 20 100 22
Output:

4