Cho \(n\) con ếch, trong đó, con ếch thứ \(i\) sẽ có bước nhảy là \(a_i\). Tất cả con ếch đều có vị trí bắt đầu là \(0\) và sau mỗi giây con ếch ở vị trí thứ \(i\) sẽ nhảy đúng độ dài \(a_i\) . Bạn chỉ được đặt \(1\) bẫy duy nhất, hãy tìm vị trí đặt bẫy sao cho bắt được nhiều ếch nhất có thể (lưu ý: vị trí đặt bẫy không vượt quá \(n\))

Dữ liệu vào:

• Dòng đầu tiên chứa một nguyên dương \(t\) là số lượng bộ test \((1 \le t \le 100)\)
• Dòng đầu tiên của mỗi bộ test là số lượng ếch \(n\) \((1 \le n \le 2 \times 10^5)\)
• Dòng thứ hai của bộ test là \(n\) số nguyên dương đại diện cho độ dài bước nhảy của từng con ếch \(a_1, a_2... a_n\) \((1 \le a_i \le 10^9)\)

Dữ liệu ra:

• \(t\) dòng, mỗi dòng là kết quả số lượng ếch bắt được tối đa của bộ test tương ứng

Input

7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10

Output

3
3
3
5
0
4
4

Giải thích

Ở test 1: đặt bẫy ở vị trí 4 sẽ bắt được tối đa 3 con ếch 1, 2 và 4.