Shubham has a binary string s. A binary string is a string containing only characters "0" and "1".

He can perform the following operation on the string any amount of times: 

  * Select an index of the string, and flip the character at that index. This means, if the character was "0", it becomes "1", and vice versa. 



A string is called good if it does not contain "010" or "101" as a subsequence — for instance, "1001" contains "101" as a subsequence, hence it is not a good string, while "1000" doesn't contain neither "010" nor "101" as subsequences, so it is a good string.

What is the minimum number of operations he will have to perform, so that the string becomes good? It can be shown that with these operations we can make any string good.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters.

Input

The first line of the input contains a single integer t (1≤ t ≤ 100) — the number of test cases.

Each of the next t lines contains a binary string s (1 ≤ |s| ≤ 1000).

Output

For every string, output the minimum number of operations required to make it good.

Example

Input


7
001
100
101
010
0
1
001100


Output


0
0
1
1
0
0
2

Note

In test cases 1, 2, 5, 6 no operations are required since they are already good strings.

For the 3rd test case: "001" can be achieved by flipping the first character — and is one of the possible ways to get a good string.

For the 4th test case: "000" can be achieved by flipping the second character — and is one of the possible ways to get a good string.

For the 7th test case: "000000" can be achieved by flipping the third and fourth characters — and is one of the possible ways to get a good string.

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Round646_Solution_2 implements Runnable {

    private boolean console=false;
    private long MOD = 1000_000_007L;
    private int MAX = 1000_001;

    private void solve1(){

        char[] arr = in.ns().toCharArray();

        int n=arr.length;

//        char[] left = new char[n];
//        char[] right = new char[n];
//

        int ans=10011;

        for(int i=0;i<n;++i){

            int cnt=0;

            for(int j=0;j<=i;++j){
                if(arr[j]!='1')
                    cnt++;
            }

            for(int j=i+1;j<n;++j){
                if(arr[j]!='0')
                    cnt++;
            }

            ans = min(ans,cnt);
            cnt = 0;

            for(int j=0;j<=i;++j){
                if(arr[j]!='0')
                    cnt++;
            }

            for(int j=i+1;j<n;++j){
                if(arr[j]!='1')
                    cnt++;
            }

            ans = min(ans,cnt);

        }

        out.println(ans);

    }

    private void solve() {
        int testCases = 1;
        testCases = in.ni();
        while (testCases-->0){
            solve1();
        }
    }

    private void add(Map<Integer,Integer> map,int key){
        map.put(key,map.getOrDefault(key,0)+1);
    }

    private void remove(Map<Integer,Integer> map,int key){
        if(!map.containsKey(key))
            return;
        map.put(key,map.getOrDefault(key,0)-1);
        if(map.get(key)==0)
            map.remove(key);
    }

    @Override
    public void run() {
        long time = System.currentTimeMillis();
        try {
            init();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        try {
            solve();
            out.flush();
            System.err.println(System.currentTimeMillis()-time);
            System.exit(0);
        }catch (Exception e){
            e.printStackTrace(); System.exit(1);
        }
    }

    /* -------------------- Templates and Input Classes -------------------------------*/

    private FastInput in;
    private PrintWriter out;
    public static void main(String[] args) throws Exception {
        new Round646_Solution_2().run();
//        new Thread(null, new Round646_Solution_2(), "Main", 1 << 27).start();
    }
    private void init() throws FileNotFoundException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        try {
            if (!console && System.getProperty("user.name").equals("puneet")) {
                outputStream = new FileOutputStream("/home/puneet/Desktop/output.txt");
                inputStream = new FileInputStream("/home/puneet/Desktop/input.txt");
            }
        } catch (Exception ignored) {
        }
        out = new PrintWriter(outputStream);
        in = new FastInput(inputStream);
    }
    private void maualAssert(int a,int b,int c){
        if(a<b || a>c) throw new RuntimeException();
    }
    private void maualAssert(long a,long b,long c){
        if(a<b || a>c) throw new RuntimeException();
    }
    private void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
    private void sort(long[] arr) {
        List<Long> list = new ArrayList<>();
        for (long object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
    private long ModPow(long x, long y, long MOD) {
        long res = 1L;
        x = x % MOD;
        while (y >= 1L) {
            if ((y & 1L) > 0) res = (res * x) % MOD;
            x = (x * x) % MOD;
            y >>= 1L;
        }
        return res;
    }
    private int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
    private long gcd(long a, long b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
    private int[] arrInt(int n){
        int[] arr=new int[n];for(int i=0;i<n;++i)arr[i]=in.ni();
        return arr;
    }
    private long[] arrLong(int n){
        long[] arr=new long[n];for(int i=0;i<n;++i)arr[i]=in.nl();
        return arr;
    }

    private int arrMax(int[] arr){
        int ans = arr[0];
        for(int i=1;i<arr.length;++i){
            ans = max(ans,arr[i]);
        }
        return ans;
    }
 
    private long arrMax(long[] arr){
        long ans = arr[0];
        for(int i=1;i<arr.length;++i){
            ans = max(ans,arr[i]);
        }
        return ans;
    }
 
    private int arrMin(int[] arr){
        int ans = arr[0];
        for(int i=1;i<arr.length;++i){
            ans = max(ans,arr[i]);
        }
        return ans;
    }
 
    private long arrMin(long[] arr){
        long ans = arr[0];
        for(int i=1;i<arr.length;++i){
            ans = max(ans,arr[i]);
        }
        return ans;
    }

    static class FastInput { InputStream obj;
        public FastInput(InputStream obj) {
            this.obj = obj;
        }
        private byte inbuffer[] = new byte[1024];
        private int lenbuffer = 0, ptrbuffer = 0;
        private int readByte() { if (lenbuffer == -1) throw new InputMismatchException();
            if (ptrbuffer >= lenbuffer) { ptrbuffer = 0;
                try { lenbuffer = obj.read(inbuffer);
                } catch (IOException e) { throw new InputMismatchException(); } }
            if (lenbuffer <= 0) return -1;return inbuffer[ptrbuffer++]; }
        String ns() { int b = skip();StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) // when nextLine, (isSpaceChar(b) && b!=' ')
            { sb.appendCodePoint(b);b = readByte(); }return sb.toString();}
        int ni() {
            int num = 0, b;boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') { minus = true;b = readByte(); }
            while (true) { if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else {
                return minus ? -num : num; }b = readByte(); }}
        long nl() { long num = 0;int b;boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') { minus = true;b = readByte(); }
            while (true) { if (b >= '0' && b <= '9') { num = num * 10L + (b - '0'); } else {
                return minus ? -num : num; }b = readByte(); } }
        private boolean isSpaceChar(int c) {
            return (!(c >= 33 && c <= 126));
        }
        int skip() { int b;while ((b = readByte()) != -1 && isSpaceChar(b)) ;return b; }
        float nf() {return Float.parseFloat(ns());}
        double nd() {return Double.parseDouble(ns());}
        char nc() {return (char) skip();}
    }

}
