3.2 Jash's Magic Stone Collection
Jash is a young wizard who has discovered a mystical cave filled with enchanted stones. Each stone is either a Light Stone (represented by 1) or a Shadow Stone (represented by 0). Jash has collected these stones and arranged them in a sequence.
The ancient magic of the cave allows Jash to perform two types of spells on his stone collection:
Vanishing Spell: Jash can make any one stone disappear from his collection. This powerful spell requires 1 Magic Coin to cast.
Swapping Spell: Jash can swap the positions of any two stones in his collection. This basic spell costs no Magic Coins (it's free!).
Jash can cast these spells as many times as he wants and in any order he desires.
The Oracle of the cave has told Jash that his stone collection becomes Perfect when no two stones at the same position have the same type as they did originally. In other words, if we call his final arrangement t, then the collection is Perfect if for each position i from 1 to |t| (where |t| is the length of the final sequence), we have t_i ≠ s_i (where s is his original collection).
Special Note: An empty collection (when Jash has made all stones vanish) is always considered Perfect by the Oracle.
Jash wants to know: What is the minimum number of Magic Coins he needs to spend to make his stone collection Perfect?
Constraints
1 ≤ t ≤ 10⁴
1 ≤ |s| ≤ 2·10⁵; s_i ∈ {0, 1}
Additional constraint: The total length of all stone collections doesn't exceed 2·10⁵.
Input Format
The first line contains a single integer t — the number of stone collections Jash wants to test.
For each test case, there is one line containing a binary string s — Jash's original stone collection, where each character represents either a Shadow Stone (0) or a Light Stone (1).
Output Format
For each test case, print one integer — the minimum number of Magic Coins Jash needs to spend to make his collection Perfect.
Example 1
Input:
4
0
011
0101110001
111100
Output:
1
1
0
4
Explanation:
Test Case 1: Jash has a single Shadow Stone "0". To make it Perfect, he must use a Vanishing Spell to make it disappear (since the empty collection is always Perfect). This costs 1 Magic Coin.
Test Case 2: Jash has stones "011". He can use a Vanishing Spell on the middle stone to get "01", then use a Swapping Spell to rearrange them to "10". Now t₁ ≠ s₁ and t₂ ≠ s₂, making the collection Perfect. Total cost: 1 Magic Coin.
Test Case 3: Jash has stones "0101110001". He can use multiple Swapping Spells: swap positions 1↔2, 3↔4, 5↔7, 6↔8, and 9↔10 to get "1010001110". All Swapping Spells are free, so the total cost is 0 Magic Coins.
Test Case 4: Jash has stones "111100". To make this collection Perfect, he needs to use 4 Vanishing Spells, costing 4 Magic Coins total.
Log In to solve the Question