B'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: 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 <= i <= j <= m , the following condition must hold: min_{i <= k <= j} s_k <= sum_{k=i}^j s_k <= max_{i <= k <= 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. The first line of input contains a single integer t ( 1 <= t <= 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 <= n <= 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 <= a_i <= 10^9 ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 1000 . For each test case, output a single integer -- the maximum number of subsegments among all possible ways to divide the array a . 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) <= (-1)+9 <= max(-1,9) . In the second test case, if Daniel divides the a'...