First character

 Prepbuddy and his friend Gaurav participated in many coding competitions and Prepbuddy always solve more questions than his friend. So his friend gave him a string

$S$ containing only four types of characters 'C', 'O', 'D' and 'E'. and challenged him to make the string $S$ balanced. The String $S$ is called balance if all characters are present $N/4$ times in the string $S$ where $N$ is the length of the string. His friend told him to print the minimum length of the substring that can be replaced with any other string of the same length to make the string $S$ balanced. Prepbuddy asks for your help to find the answer. Note:- Print $0$ if the string is already balanced.

Note: Strings contains only 'C', 'O', 'D' and 'E' The length of the string should be multiple of $4$.

Input Format

The first line of the input contains an integer $T$ denoting the number of test cases. Then $T$ test cases follow. Each test case contains a string $S$.

Output Format

#Solutions in JAVA

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
    
    //write your code here
      BufferedReader s = new BufferedReader(new
        InputStreamReader(System.in));
    int t=Integer.parseInt(s.readLine());
    while(t--!=0)
    {
      
      String str=s.readLine();
      int n=str.length();
      int count1=0,count2=0,count3=0,count4=0;
      for(int i=0;i<n;i++)
      {
        if(str.charAt(i)=='C')
        {
          count1++;
        }
         if(str.charAt(i)=='O')
        {
          count2++;
        }
         if(str.charAt(i)=='D')
        {
          count3++;
        }
         if(str.charAt(i)=='E')
        {
          count4++;
        }
      }
     
        int res=0;
          int n4=n/4;
          if(count1>n4)
          {
            res+=n4-count1;
          }
            if(count2>n4)
          {
            res+=n4-count2;
          }
            if(count3>n4)
          {
            res+=n4-count3;
          }
            if(count4>n4)
          {
            res+=n4-count4;
          }
      
      System.out.println(Math.abs(res));
    }
  }
}

For each test case print the minimum length of the substring that can be replaced with any other string of the same length to make the original string $S$ balanced, print $0$ if the string is already balanced.

Constraint

$1<=T<=100$ $1<=N<={10}^5$, $N$ is the length of string

Time Limit

1 second

Example

Input

3 CODE CCOD EDDCDCEE

Output

0 1 2

Explanation

In the first test case,
Input: S = "CODE"
Output: 0
Explanation: S is already balanced.

In the second test case,
Input: S = "CCOD"
Output: 1
Explanation: We need to replace a 'C' to 'E', so that "CEOD" (or "ECOD") is balanced

In the third test case,
Input: S = "EDDCDCEE"
Output: 2
Explanation: We need to replace  'ED' to 'OO', so that "OODCDCEE"  is balanced.