Longest Negative Product Subsequence

You are given T test cases. In each test case, you are provided with a sequence of n integers. Your task is to find the length of the longest contiguous subsequence such that the product of every adjacent pair of numbers is negative.

More formally, given a subsequence \(a_1, a_2, \dots, a_k\), it is considered valid if for every \(1 \le i < k\) the product \(a_i \times a_{i+1}\) is negative. If no two consecutive elements satisfy this condition, the answer is 1 (since every individual element is a subsequence of length 1). For an empty sequence, the answer is 0.

Note: The subsequence must be contiguous, meaning it is obtained by removing some (possibly none or all) elements from the beginning and the end of the original sequence.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer n (the length of the sequence), followed by a line containing n space-separated integers.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest contiguous subsequence in which the product of every pair of adjacent numbers is negative.## sample

5
6
1 -2 3 -4 5 -6
5
-1 -2 -3 -4 -5
4
1 2 3 4
2
3 -2
1
5

6
1
1
2
1