Split Binary String Problem Statement

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

Example:

Beautiful Strings:

0011, 1100, 101010

Non-Beautiful Strings:

1110, 0001, 10101

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.

Example:

Input:

str = "101001"

Output:

3

Explanation:

The string can be divided into 3 beautiful strings: "10", "10", and "01".

Input:

The first line 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:

For each test case, return the maximum number of substrings that '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.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• Time limit: 1 second

Note:

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