You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
Tom is waiting for his results of Zhongkao examination. To ease the tense atmosphere, his friend, Daniel, decided to play a game with him. This game is called "Divide the Array".

The game is about the array $$$a$$$ consisting of $$$n$$$ integers. Denote $$$[l,r]$$$ as the subsegment consisting of integers $$$a_l,a_{l+1},\ldots,a_r$$$.

Tom will divide the array into contiguous subsegments $$$[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$$$, such that each integer is in exactly one subsegment. More formally:

- For all $$$1\le i\le m$$$, $$$1\le l_i\le r_i\le n$$$;
- $$$l_1=1$$$, $$$r_m=n$$$;
- For all $$$1< i\le m$$$, $$$l_i=r_{i-1}+1$$$.

Denote $$$s_{i}=\sum_{k=l_i}^{r_i} a_k$$$, that is, $$$s_i$$$ is the sum of integers in the $$$i$$$-th subsegment. For all $$$1\le i\le j\le m$$$, the following condition must hold:

$$$$$$ \min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k. $$$$$$

Tom believes that the more subsegments the array $$$a$$$ is divided into, the better results he will get. So he asks Daniel to find the maximum number of subsegments among all possible ways to divide the array $$$a$$$. You have to help him find it.

## Input Format
The first line of input contains a single integer $$$t$$$ ($$$1\le t\le 50$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 300$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

## Output Format
For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $$$a$$$.

## Examples
```input
8
3
-1 5 4
2
2023 2043
6
1 4 7 -1 5 -4
5
-4 0 3 -18 10
1
998244853
10
-4 2 5 -10 4 8 2 9 -15 7
7
-7 3 8 -9 -2 2 4
4
-5 5 -2 -5
```
```output
2
1
3
2
1
6
5
3
```

## Note
In the first test case, Daniel can divide the array into $$$[-1]$$$ and $$$[5,4]$$$, and $$$s=[-1,9]$$$. It can be shown that for any $$$i=j$$$, the condition in the statement is already satisfied, and for $$$i=1,j=2$$$, we have $$$\min(-1,9)\le (-1)+9\le \max(-1,9)$$$.

In the second test case, if Daniel divides the array into $$$[2023]$$$ and $$$[2043]$$$, then for $$$i=1,j=2$$$ we have $$$2023+2043>\max(2023,2043)$$$, so the maximum number of subsegments is $$$1$$$.

In the third test case, the optimal way to divide the array is $$$[1,4,7],[-1],[5,-4]$$$.

In the fourth test case, the optimal to divide the array way is $$$[-4,0,3,-18],[10]$$$.

In the fifth test case, Daniel can only get one subsegment.

Now solve the problem and return the code.