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_{i_1}~, ~A_{i_2}~, ..., ~A_{i_M}~ thỏa mãn: ~1 \le i_1 < i_2 < \dots < i_M \le 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 \ge 3~.

Input

• Dòng ~1~: ~T~ - số test ~(1 \le T \le 15)~.

• Tiếp theo là ~2T~ 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