该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

题目描述

在一个神秘的世界中，给定一个由0和1组成的二进制字符串。你有两种变换方式：将一个0变成1，或将一个1变成0。你的目标是找到将二进制字符串S转换为有序二进制字符串（有序二进制字符串是指所有的0都出现在所有的1之前）所需的最少变换次数。

输入格式

第一行包含一个整数T，表示测试数据的组数。（1 ≤ T ≤ 10）

以下T行，每行包含一个二进制字符串S，对应一个测试案例。

输出格式

对于每个测试案例，输出将字符串S转换为有序二进制字符串所需的最少变换次数。

样例

输入

3
000111
010001
100000
    

输出

0
1
1
    

数据范围与提示

10%: |S| ≤ 2，T ≤ 5

30%: |S| ≤ 3，T ≤ 5

50%: |S| ≤ 10，T ≤ 10

80%: |S| ≤ 1000，T ≤ 10

100%: |S| ≤ 100000，T ≤ 10

|S|表示S的长度。

样例