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 python3.

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:
```python
<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.