SKFIB - Dãy số dài nhất

Giới hạn
  • Thời gian: 0.6s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

  • Người up: skyvn97
  • Nguồn bài: IOICAMP