Given a sorted array of integers, find the number of negative numbers.

Expected Time Complexity: O(log n)

Examples

Array: [-5, -3, -2, 3, 4, 6, 7, 8]
Answer: 3

Array: [0, 1, 2, 3, 4, 6, 7, 8]
Answer: 0

Testing

Input Format

The first line contains 'T' denoting the no. of test cases.

T lines each contain a number 'n' denoting the number of elements, followed by n space-separated numbers denoting the array elements.

Output Format

T lines each contain an integer denoting the number of negative numbers for that test case.

Sample Input

2
8 -5 -3 -2 3 4 6 7 8
8 0 1 2 3 4 6 7 8

Expected Output

3
0

Constraints

1 <= T <= 100

1 <= n <= 104

-105 <= Ai <= 105