Sâu trong vùng hoang dã, Zhily và Jily đã phát hiện ra một loạt các địa điểm tụ họp chứa đựng logic trừu tượng. Một số địa điểm tụ họp này lại chứa những lỗi không nhất quán trong logic của chúng, có thể sụp đổ bất cứ lúc nào. Họ hy vọng sẽ truyền tải logic giữa các địa điểm tụ họp liền kề thông qua các phương thức chuyển giao hợp lý để càng nhiều địa điểm tụ họp càng tốt cuối cùng có thể khôi phục lại sự ổn định logic.

• Bạn được cho một dãy \(a\) gồm \(n\) số nguyên. Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy thích:
  Chọn một chỉ số \(i\) \((1 \le i < n)\) và gán \({a_i} = {a_i} + {a_{i+1}}\)
• Mỗi chỉ số chỉ được chọn \(một\) \(lần\)
• Tìm số lượng phần tử nguyên dương lớn nhất trong mảng cuối cùng sau khi thực hiện tất cả các phép toán.

Input

• Mỗi test có nhiều truy vấn. Dòng đầu tiên chứa số truy vấn \(t\) \((1 \le t \le 10^4)\).
• Dòng đầu tiên của mỗi truy vấn chứa một số nguyên \(n\) \((2 \le n \le 2 \cdot 10^5)\).
• Dòng thứ hai của mỗi truy vấn chứa \(n\) số nguyên \({a_1},{a_2},...,{a_n}\) \((-10^9 \le {a_i} \le 10^9)\)
• Tổng \(n\) của từng truy vấn luôn không quá \(2 \cdot 10^5\)

Output

• Với mỗi truy vấn, chỉ xuất ra một dòng duy nhất chứa một số nguyên \(k\), là số lượng các số dương trong dãy cuối cùng.

Example

4
5
0 -1 3 -3 0
5
0 -2 1 2 3
5
0 1 0 1 0
2
1000000000 -1000000000

3
5
4
1