Split Binary String

Chintu has a long binary string ‘str’. A binary string is a string that contains only 0 and 1. He considers a string ‘beautiful’ if and only if the number of 0's and 1's in the string are equal.

For example :

0011 , 1100 , 101010 etc are beautiful strings whereas 1110, 0001,10101 etc are not beautiful strings.

Now Chintu wants to split the string into substrings such that each substring is beautiful. Can you help Chintu to find the maximum number of beautiful strings he can split the string into? If it is not possible to split the string in such a way that all strings are beautiful, return -1.

For example :

Let the given string be “101001”
We will return 3 as we can divide the string into 3 beautiful strings “10” “10” and “01’.

Input Format :

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains the string ‘str’.        

Output Format :

For each test case, return the maximum number of substrings, ‘str’ can be split into such that each substring is beautiful.

If there are none, return -1.

Output for each test case will be printed in a new line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 5000

Time limit: 1 second