Minimal Closing Brackets Required

You are given T test cases. Each test case is a binary string composed of characters '1' and '0'. Interpret '1' as an open bracket ( and '0' as a closing bracket ). A valid bracket sequence is one where every open bracket has a corresponding closing bracket. Your task is to determine the minimum number of closing brackets ) that need to be appended to the end of each string to transform it into a balanced bracket sequence.

For each test case, process the string from left to right. Increment a counter for each '1' encountered, and for each '0', decrement the counter if it is greater than zero. The counter at the end of the string represents the number of unmatched open brackets, and hence the number of closing brackets required to balance the sequence.

Mathematically, if after processing the string the count of unmatched open brackets is \(c\), then the answer is \(c\).

inputFormat

The first line of input contains an integer t (\(1 \leq t \leq 10^5\)) denoting the number of test cases. Each of the following t lines contains a binary string composed only of characters '1' and '0'.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of closing brackets ) that must be appended to the end of the string to form a balanced bracket sequence.

## sample

4
1100
101
1
111

0
1
1
3

</p>