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.BufferedReader;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static long MOD = 1000000007;
    static int modulo=998244353;
    static int parent[];
    static boolean visited[][];
    public static void main(String[] args) {
       boolean prime[]=new boolean[(int)1e6+1];
       for(int i=0;i<=1e6;i++)
           prime[i]=true;
       
       for(int i=2;i*i<=1e6;i++){
           if(prime[i]==true){
           for(int j=i*i;j<=1e6;j+=i){
               prime[j]=false;
           }
           }
       }
       ArrayList<Integer> list=new ArrayList<>();
       for(int i=2;i<=1e6;i++){
           if(prime[i]==true)
               list.add(i);
       }
      
       
       Scanner in = new Scanner(System.in);
       int test=in.nextInt();
       while(test-->0){
       String s=in.next();
       
       int one=0;
       int zero=0;
       for(int i=0;i<s.length();i++){
           if(s.charAt(i)=='0')
               zero++;
           else
               one++;
       }
           
       int co=0;
       int cz=0;
       int ans=Math.min(zero,one);
       for(int i=0;i<s.length();i++){
           if(s.charAt(i)=='0')
               cz++;
           if(s.charAt(i)=='1')
               co++;
           
           ans=Math.min(cz+one-co,ans);
           
           ans=Math.min(co+zero-cz,ans);
       }
       System.out.println(ans);
      
       }
       
           }

    
               
           
           
       
           
       
    
   public static void dfsMatrix(char arr[][],int i,int j,ArrayList<pair> connect){
       visited[i][j]=true;
       if(arr[i][j]=='*' ){
           connect.add(new pair(arr[i][j],i,j));
       
       if(i+1<arr.length){
           if(visited[i+1][j]==false)
           dfsMatrix(arr,i+1,j,connect);
       }
       if(j+1<arr[0].length){
           if(visited[i][j+1]==false)
           dfsMatrix(arr,i,j+1,connect);
           
       }
       if(i-1>=0){
           if(visited[i-1][j]==false)
           dfsMatrix(arr,i-1,j,connect);
       }
       if(j-1>=0){
           if(visited[i][j-1]==false)
           dfsMatrix(arr,i,j-1,connect);
       }
       }
       else{
           return;
       }
   }
    public static boolean union(int u,int v){
        int par1=findRoot(u);
        int par2=findRoot(v);
        
        if(par1!=par2){
            par1=parent[par2];
            return true;
        }
        
        return false;
    }
    public static int findRoot(int u){
        while(parent[u]!=u)
            u=parent[u];
        
        return u;
    }
    public static void dfs(int curr,int parent,int height[],ArrayList<Integer> arr[])
{
		for(int i:arr[curr])
		{
			if(i!=parent){
				height[i]=height[curr]+1;
				dfs(i,curr,height,arr);
			}
		}	

}
    public static double bs( double w,double min1,double min2,int n){
        double left=0;
        double right=w;
        double ans=0;
        int i=0;
        while(i<=100){
            double mid=(left+right)/2;
            if(mid<=min1 && 2*mid<=min2 && 3*n*mid<=w){
                ans=n*mid+2*n*mid;
                left=mid;
            }
            else{
                right=mid;
            }
            i++;


        }
        return ans;
        
    }
    
     public static boolean check (double time,long x[],long r[],int N) {
   
      double l = x[0]-r[0]*time;
      double h = x[0]+r[0]*time;
      for (int k=1; k<N; k++) {
         //System.out.println(l+" "+h+" "+(x[k]-r[k]*time)+" "+(x[k]+r[k]*time));
         if ((x[k]-r[k]*time)>h || (x[k]+r[k]*time)<l)
            return false;
         //update bounds if neccessary
         if ((x[k]-r[k]*time)>l)
            l=x[k]-r[k]*time;
         if ((x[k]+r[k]*time)<h)
            h=x[k]+r[k]*time;
      }
      return true;
   }
    
     public static int solve(int n,int m,ArrayList<pair> list1,int k){
         int low=1;
         int high=n*m;
         int a=0;
         while(low<=high){
             int mid=(low+high)/2;
             int ans[][]=create(n,m,list1,mid);
//             for(int i=0;i<=n;i++){
//                 for(int j=0;j<=m;j++){
//                     System.out.print(ans[i][j]+" ");
//                 }
//                 System.out.println();
//             }
             int pre[][]=prefix(n,m,ans);
             
             if(check(pre,n,m,k)){
                 
                 if(mid%2==1)
                     a=1;
                 else
                     a=-1;
                 
                 high=mid-1;
             }
             else
                 low=mid+1;
         }
         
         return a;
     }
     public static int [][] prefix(int n,int m,int arr[][]){
         int ans[][]=new int[n+1][m+1];
         for(int i=1;i<=n;i++){
             for(int j=1;j<=m;j++){
                 ans[i][j]=arr[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
             }
         }
         return ans;
         
     }
     public static int[][] create(int n,int m,ArrayList<pair> list1,int mid){
         int arr[][]=new int[n+1][m+1];
         
             for(int i=0;i<mid;i++){
                 if(i%2==0)
                 arr[list1.get(i).x][list1.get(i).y]=1;
                 else
                  arr[list1.get(i).x][list1.get(i).y]=-1;   
             } 
             
             return arr;
     }
     public static boolean check(int arr[][],int n,int m,int k){
         
         int ans=0;
         for(int i=k;i<=n;i++){
             
             for(int j=k;j<=m;j++){
                 ans=arr[i][j]-arr[i][j-k]-arr[i-k][j]+arr[i-k][j-k];
             }
            
             
             if((int)Math.abs(ans)==k*k)
                 return true;
         }
         return false;
     }
     public static int[][] rotateGrid(int[][] grid, int k) {
        int top=0;
        int left=0;
        int bottom=grid.length-1;
        int right=grid[0].length-1;
        
        while(bottom>top&&right>left){
        int elements=2*(right-left+1)+2*(bottom-top+1)*2-4;
        
        int t=k%elements;
        
        while(t-->0){
            int temp = grid[top][left];
            for(int j = left; j<right; j++){
                grid[top][j] = grid[top][j+1];
            }
            for(int i = top; i<bottom; i++){
                grid[i][right] = grid[i+1][right];
            }
            for(int j = right; j>left; j--){
                grid[bottom][j] = grid[bottom][j-1]; 
            }
            for(int i = bottom; i>top; i--){
                grid[i][left] = grid[i-1][left];
            }
            grid[top+1][left]=temp;
        }
        top++;
        left++;
        right--;
        bottom--;
        
    }
        return grid;
    }
    
    public static void solve1(int n,int arr[]){
        int b[]=new int[2*n+1];
        for(int i=0;i<n;i++){
            b[arr[i]]=i+1;
        }
        int count=0;
        for(int i=3;i<2*n;i++){
        for(int j=1;j*j<i;j++){
            if(i%j==0 && i!=j*j){
                if(b[j]+b[i/j]==i){
                    count++;
                }
            }
        }
    }
        System.out.println(count);
    }
    public static long modpow(long a, long b){
	    if(b==0){
	        return 1;
	    }
	    long x = modpow(a, b/2);
	    x = (x*x)%modulo;
	    if(b%2==1){
	        return (x*a)%modulo;
	    }
	    return x;
	}
    public static long factorial(long n){
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 6;
        return n*factorial(n-1);
    }
    public static long benches(int n){
        return ncr(n,5)*n*(n-1)*(n-2)*(n-3)*(n-4);
    }
    public static long ncr(int n,int r){
        long dp[][]=new long[n+1][r+1];
        
        for(int i=0;i<=n;i++){
            for(int j=0;j<=Math.min(i,r);j++){
                if(j==0 ||j==i)
                    dp[i][j]=1;
                else{
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                }
            }
        }
        
        return dp[n][r];
    }
    public static  long select(int n){
    return ncr(n,5)+ncr(n,6)+ncr(n,7);

    }
    public static long ncr1(int n,int r){
        long k=Math.max(r,n-r);
        long num=1;
        long den=1;
        long j=1;
        
        for(long i=n;i>k;i--){
            num*=i;
            den*=j;
            j++;
        }
        return num/den;
    }
    public static int countDiff(int arr[],int n,int diff){
        int sum=0;
       
        for(int i=0;i<n;i++){
            
            sum+=arr[i];
        }
        
        int max=sum/2;
        
        boolean dp[][]=new boolean[n+1][max+1];
        
        for(int i=0;i<=n;i++){
            for(int j=0;j<=max;j++){
                if(i==0)
                    dp[i][j]=false;
                if(j==0)
                    dp[i][j]=true;
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=max;j++){
                if(arr[i-1]<=j)
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-arr[i-1]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        int min=0;
        int count=0;
        for(int j=0;j<=max;j++){
            min=0;
            if(dp[n][j]==true){
                min=sum-2*j;
                if(min==diff)
                    count++;
            }
        }
        
        return count;
    }
    public static long permutation(long n,long r){
        if(n==0)
            return 1;
        
        long ans=n;
        for(long i=n-1;i>(n-r);i--){
            ans=(ans*i)%MOD;
        }
        return ans;
    }
    public static int minimumDiff(int arr[],int n){
        int sum=0;
       
        for(int i=0;i<n;i++){
            
            sum+=arr[i];
        }
        
        int max=sum/2;
        
        boolean dp[][]=new boolean[n+1][max+1];
        
        for(int i=0;i<=n;i++){
            for(int j=0;j<=max;j++){
                if(i==0)
                    dp[i][j]=false;
                if(j==0)
                    dp[i][j]=true;
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=max;j++){
                if(arr[i-1]<=j)
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-arr[i-1]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        int min=Integer.MAX_VALUE;
        for(int j=0;j<=max;j++){
            if(dp[n][j]==true){
                min=Math.min(min,sum-2*j);
            }
        }
        
        return min;
    }
    public static int findTargetSumWays(int[] nums, int target) {
        int n=nums.length;
         int dp[][]=new int[n+1][target+1];
         
         for(int i=0;i<=n;i++){
             for(int j=0;j<=target;j++){
                 if(i==0)
                 dp[i][j]=0;
                 
                 if(j==0)
                     dp[i][j]=1;
             }
         }
         
         for(int i=1;i<=n;i++){
             for(int j=1;j<=target;j++){
                 if(nums[i-1]<=j)
                     dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                 else
                     dp[i][j]=dp[i-1][j];
             }
         }
         
//         for(int i=0;i<=n;i++){
//             for(int j=0;j<=target;j++){
//                 System.out.print(dp[i][j]+" ");
//             }
//             System.out.println();
//         }
         
         return dp[n][target];
         
    }
    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        else
            return gcd(y % x, x);
    }
    public static long lcm(long x, long y) {
        return (x * (y / gcd(x, y)));
    }
    static int equalPartition(int n, int arr[],int sum)
    {
       
       
      
           int max=sum;
           boolean dp[][]=new boolean[n+1][max+1];
           
           for(int i=0;i<=n;i++){
               for(int j=0;j<=max;j++){
                   if(i==0)
                   dp[i][j]=false;
                   if(j==0)
                   dp[i][j]=true;
               }
           }
           
           for(int i=1;i<=n;i++){
               for(int j=1;j<=max;j++){
                   if(arr[i-1]<=j){
                       dp[i][j]=(dp[i-1][j]||dp[i-1][j-arr[i-1]]);
                   }
                   else{
                       dp[i][j]=dp[i-1][j];
                   }
               }
           }
           
           for(int i=0;i<=n;i++){
               for(int j=0;j<=max;j++){
                   System.out.print(dp[i][j]+" ");
               }
               System.out.println();
           }
           int count=0;
           for(int i=0;i<=n;i++){
            if(dp[i][max]==true){
               
                count++;
            }
            
        }
        return count;
       }
    
    public static long power(long base,long power){
        long res=1;
        while(power!=0){
            if(power%2==0){
                power/=2;
                base=(base*base);
            }
            else{
                power--;
                res=(res*base);
            }
            
        }
        return res;
    }
}
class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
 
		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
	}
class pair 
	    {
                char a;
	        int x;
	        int y;
 
	        pair(char a,int x, int y) {
                    this.a=a;
	            this.x = x;
	            this.y = y;
	        }
	        
}