You are given an array having \(n\) elements. In one operation, you can make \(a[i]=a[i]*(-1)\), that is, you can change a positive number into a negative number and vice versa. You can use this operations for several times.

Your task is to print the minimum number of operations that are required to make the sum of elements of array zero.

Input format

The first line contains \(t\) denoting the number of test cases. \(1⩽t⩽10\)
The first line of each test case contains \(n\) denoting the size of the array. \(0<n⩽10^{3}\)
The second line of each test case contains \(n\) denoting the elements of the array. \(-10^{3}⩽a[i]⩽10^{3}\)

Output format

In a new line, print the minimum number of operations that required to make the sum of elements zero. Otherwise, print \(-1\) if you cannot make the sum of elements in array zero after applying many operations.

Note: The absoulte value of the sum of the elements of the array in input is not more than \(10^3\).