Problem Description

Author: eedwang

身為百鬼あやめ的老公。今天我跟她在玩一個小遊戲：

我們家裡有一排燈，每個燈的狀態用一個字串 s 表示： - '0' 代表燈是關的 - '1' 代表燈是亮的

你們的遊戲規則是：

• 每次操作，可以選擇一個燈 a ，而選中的燈會被翻轉： '0' → '1'，'1' → '0'

而遊戲的目的是把所有燈關掉，這樣我才能跟百鬼あやめ做愛做的事。

要關好燈出門才省電，我先去跑步了。

Input Format

第一行輸入整數 t (1 ≤ t ≤ 10⁴) -- 表示測資筆數 接下來每組測資一行，包含字串 s (1 ≤ s的長度 ≤ 50)

Output Format

對每組測資，輸出最少操作次數。

5
1
000
1001
10101
01100101011101

1
0
2
3
8