Cho dãy ~A~ gồm ~N~ số nguyên. Một dãy con của ~A~ là 1 dãy gồm các phần tử: ~A[i_1]~, ~A[i_2]~, ~\dots~, ~A[i_M]~ thỏa mãn: ~1 \le i_1 < i_2 < \dots < i_M \le N~. Tìm dãy con B của A dài nhất thỏa mãn điều kiện:

~B[i] = B[i-1] + B[i-2]~ với mọi i >= 3.

Input

1. Dòng 1: ~T~ - số test ~(1 \le T \le 15)~.
2. Tiếp theo là ~2 \times T~ dòng mô tả các test, mỗi test gồm:
   • Dòng 1: ~N \, (3 \le N \le 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.

Sample Input

1
7
-20 87 20 0 20 100 22

Sample Output

4