C. Binary String（求前缀和）

You are given a string ss consisting of characters 0 and/or 1.

You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values:

• the number of characters 0 left in the string;
• the number of characters 1 removed from the string.

What is the minimum cost of removal you can achieve?

Input

The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.

Each test case consists of one line containing the string ss (1≤|s|≤2⋅1051≤|s|≤2⋅105), consisting of characters 0 and/or 1.

The total length of strings ss in all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, print one integer — the minimum cost of removal you can achieve.

Example

input

Copy

5
101110110
1001001001001
0000111111
00000
1111

output

Copy

1
3
0
0
0

Note

Consider the test cases of the example:

1. in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is 11;
2. in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is 33;
3. in the third test case, it's optimal to remove four characters from the beginning;
4. in the fourth test case, it's optimal to remove the whole string;
5. in the fifth test case, it's optimal to leave the string as it is.

题意：

给你一个01字符串，你可以从前或者从后删除一些字符串，那么你最后的成本将是你删除过后的字符串中剩余0的数量，或者是你删除过程中删除1的数量，两者中的最大值 。

思路：

我们先想一下最优的效果，我们尽可能让1留下，让0自行被删除 。

所以我们首先统计字符串中0的个数。

因为我们最优得效果就是全部.剩下的是1，我们设0的个数是x，字符串的长度是l所以我们挨着遍历（l-x）的每个区间剩下0的个数的最小值就是我们的答案

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long

using namespace std;

const int N = 2e5 + 10;

string s;
int v[N];

void solve()
{
     cin >> s;
     int len = s.size();

     for(int i = 1; i <= len; i ++)
     {
          v[i] = v[i-1]+(s[i-1] == '0');
          //cout << i << " : " << v[i] << endl;
     }

     int ans = 1e9;
//j=len-v[n] ???????
     for(int i = 1, j = len - v[len]; i <= len && j <= len; i ++, j++)
          ans = min(ans, v[j]-v[i-1]);
    //
 cout << ans << '\n';
}

signed main()
{
     IOS;
     int T;
     cin >> T;
     while(T--)
          solve();
     return 0;
}