Divide Array into Contiguous Subarrays with Uniform Signs

You are given an array of integers \(A = [a_1, a_2, \dots, a_n]\). Your task is to divide this array into the minimum number of contiguous subarrays such that in each subarray, every element is either non-negative or non-positive. Formally, for every subarray \(S\), either \(\forall x \in S, x \ge 0\) or \(\forall x \in S, x \le 0\) holds. Note that zero is considered non-negative.

For example, consider the array [1, 2, -3, -4, 5]. It can be segmented into the subarrays [1, 2], [-3, -4] and [5]. Thus, the answer is 3.

The goal is to determine the minimum number of such contiguous segments for a given array.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
N_1
a_1 a_2 ... a_{N_1}
N_2
a_1 a_2 ... a_{N_2}
... 
N_T
a_1 a_2 ... a_{N_T}

Where:

• T is the number of test cases.
• For each test case, the first line contains the integer N (the number of elements in the array).
• The second line contains N space-separated integers.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of contiguous subarrays into which the array can be divided such that each subarray contains numbers having uniform sign (all non-negative or all non-positive).

## sample

1
5
1 2 -3 -4 5

3

</p>