"Everything in the universe is balanced. Every disappointment you face in life will be balanced by something good for you! Keep going, never give up."
Let's call a string balanced if all characters that occur in this string occur in it the same number of times.
You are given a string $S$; this string may only contain uppercase English letters. You may perform the following operation any number of times (including zero): choose one letter in $S$ and replace it by another uppercase English letter. Note that even if the replaced letter occurs in $S$ multiple times, only the chosen occurrence of this letter is replaced.
Find the minimum number of operations required to convert the given string to a balanced string.
-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$.
-----Output-----
For each test case, print a single line containing one integer ― the minimum number of operations.
-----Constraints-----
- $1 \le T \le 10,000$
- $1 \le |S| \le 1,000,000$
- the sum of $|S|$ over all test cases does not exceed $5,000,000$
- $S$ contains only uppercase English letters
-----Subtasks-----
Subtask #1 (20 points):
- $T \le 10$
- $|S| \le 18$
Subtask #2 (80 points): original constraints
-----Example Input-----
2
ABCB
BBC
-----Example Output-----
1
1
-----Explanation-----
Example case 1: We can change 'C' to 'A'. The resulting string is "ABAB", which is a balanced string, since the number of occurrences of 'A' is equal to the number of occurrences of 'B'.
Example case 2: We can change 'C' to 'B' to make the string "BBB", which is a balanced string.
# cook your dish here
n=int(input())
def find(arr,num):
 auxarr=[0]*(len(arr)-sum(arr)//num)+[num]*(sum(arr)//num)
 ans=sum([abs(auxarr[i]-arr[i]) for i in range(len(arr))])/2
 return ans
letters=['A','B','C','D','E','F','G','H','I',
   'J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for _ in range(n):
 string=list(input())
 length=len(string)
 dic={letter:0 for letter in letters}
 for letter in string:
  dic[letter]+=1
 arr=[dic[letter] for letter in letters]
 arr.sort()
 currentmin=float("inf")
 for i in range(length//26,length+1):
  if i==0:
   continue
  if length%i==0 and i!=0:
   currentmin=min(currentmin,find(arr,i))
 print(int(currentmin))
 

# cook your dish here
n=int(input())
def find(arr,num):
 auxarr=[0]*(len(arr)-sum(arr)//num)+[num]*(sum(arr)//num)
 ans=sum([abs(auxarr[i]-arr[i]) for i in range(len(arr))])/2
 return ans
letters=['A','B','C','D','E','F','G','H','I',
   'J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for _ in range(n):
 string=list(input())
 length=len(string)
 dic={letter:0 for letter in letters}
 for letter in string:
  dic[letter]+=1
 arr=[dic[letter] for letter in letters]
 arr.sort()
 currentmin=float("inf")
 for i in range(length//26,length+1):
  if i==0:
   continue
  if length%i==0 and i!=0:
   currentmin=min(currentmin,find(arr,i))
 print(int(currentmin))
 
