"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.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin
from collections import Counter

def func(arr,n,l):
 count=0
 k=l//n
 if n<len(arr):
  for ele in arr[0:n]:
   count+=max(0,k-ele)
 else:
  for ele in arr:
   count+=max(0,ele-k)
 return count 

for _ in range(int(stdin.readline())):
 s=stdin.readline().strip()
 d=Counter(s)
 arr=sorted(list(d.values()),reverse=True)
 l=len(s)
 val=[1]
 for i in range(2,27):
  if l%i==0:
   val.append(i)

 ans = float('inf')
 for ele in val:
  x = func(arr,ele,l)
  if x < ans:
   ans = x
 print(ans) 


def hash_it(arr, s): # to count occurences of each letter and returning a     reverse sorted array
 for i in range(len(s)):
  arr[ord(s[i]) - 65] += 1 # counting occurences of each letter
 arr = sorted(arr, reverse = True) # reverse sorting the array
 return arr
def balance(s, arr, l): # balancing the string
 val = len(set(s))
 res = 10000000000
 pp = 0
 for p in range(1,27):
  ptr = 0
  if l % p == 0:
   var = l // p
   for q in range(p):
    if arr[q] > var:
     ptr += arr[q] - var
   for q in range(p,26):
    if arr[q] > 0:
     ptr += arr[q]
   res = min(ptr,res)
  pp += 1
 if pp == 26:
  pp = 0 
 return(res) 
 
for _ in range(int(input())): # number of test cases
 s = input() # input string
 l = len(s) # length of the string
 if l <= 2: # if length is 2 or less, it is already balanced
  print(0)
  continue
 arr = [0 for i in range(0,27)]
 arr = hash_it(arr,s)
 print(balance(s, arr, l))
 
 
 
 
 
 
  


t = int(input())
S = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
while t > 0:
 max=1000000
 s=input()
 d={}
 ll=[]
 for str in S:
  d[str]=0
 for i in range(1,27):
  if len(s) % i==0:
   ll.append(i)
 for i in s:
  d[i]+=1
 l=sorted(d.items(), key=lambda ele: ele[1], reverse=True)
 i=0; ans=0
 while i < len(ll):
  cnt=len(s) // ll[i]
  for j in range(ll[i]):
   if l[j][1] < cnt:
    ans+=cnt-l[j][1]
  i+=1
  if ans < max:
   max=ans
  ans=0
 print(max)
 t -= 1

import numpy as np
from math import floor
def getFactors(n):
 factors=[];

 for i in range(1, n + 1):
  if (n % i == 0 and (n/i)<27):
   factors.append(i)
 #print(factors)
 return factors

t=input()
t=int(t)
while(t>0):
 t-=1
 s=input()
 n=len(s)
 fact=getFactors(n)
 str=list(s)
 #print(fact)
 tot=0
 u, c = np.unique(str, return_counts=True)
 
 c[::-1].sort()
 #print(c)
 c_sum=c.sum()
 c_size=len(c)
 
 min=100000000
 #  print(length_c)
 for i in fact:
  tot=0
  k=floor(c_sum/i)
  #print(k)
  if(k<c_size):
   for j in range(k):
    if(c[j]-i>0):
     tot+=c[j]-i
   for j in range(k,c_size):
    tot+=c[j]
  #    print(tot)
  else:
   for j in c:
    if(j-i>0):
     tot+=j-i
  #    print(tot)
  if(tot<min):
   min=tot
  
#       print(min)

 print(min) 

# cook your dish here
from collections import Counter
t=int(input())
for i in range(t):
 s=input()
 c=Counter(s)
 l=list(c.values())
 l.sort(reverse=True)
 it=sum(l)
 k=len(l)
 ans=999999999
 while(k>=1):
  if(it%k==0):
   p=it//k
   sumi=0
   for j in range(len(l)):
    if(l[j]>p):
     sumi+=l[j]-p
    else:
     if(j>=k):
      sumi+=l[j]
   if(sumi<ans):
    ans=sumi
  k-=1
 k=len(l)+1
 while(k<=26 and k<=len(s)):
  if(it%k==0):
   p=it//k
   sumi=0
   for j in range(len(l)):
    if(l[j]>p):
     sumi+=l[j]-p
    else:
     break
   if(sumi<ans):
    ans=sumi
  k+=1
 print(ans)


# cook your dish here
for i in range(int(input())):
 s=input()
 l=[0 for i in range(26)]
 for i in s:
  l[ord(i)-65]+=1 
 l.sort()
 n=len(s)
 ans=float('inf')
 for i in range(1,27):
  temp=0
  if(n%i==0):
   p=n//i 
   for j in range(26-i):
    temp+=l[j]
   for j in range(26-i,26):
    if(l[j]>p):
     temp+=l[j]-p 
   ans=min(ans,temp)
 print(ans)
    


# cook your dish here
import sys
R = lambda :list(map(int,input().split()))
t = int(input())
for _ in range(t):
 string = input()
 n = len(string)
 a = [0]*26
 for i in string:
  a[ord(i)-ord('A')]+=1
 rev_lst = sorted(a,reverse=True)
 ans = n
 for i in range(1,27):
  if n%i==0:
   x = int(n/i)
   y = 0
   for j in range(0,i):
    y+=min(rev_lst[j], x)
   ans = min(ans,n-y)

 print(ans)



# 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))
 


for t in range(int(input())):
 s = input()
 l = sorted([char for char in s])
 i = 0; x =[] 
 cnt = 1
 while(i<len(l)-1):
  if(l[i]!=l[i+1]):
   x.append(cnt)
   cnt = 0
  cnt = cnt+1
  i = i+1
 x.append(cnt) 
 #print(l,"\n",x)
 m=0
 for k in range(len(x),27):
  #print(sum(x),i)
  if(sum(x)%k==0):
   m = sum(x)//k
   #print(m,i)
   break
 z = [max(0,a - m) for a in x] 
   
 for i in range(len(x),0,-1):
  #print(sum(x),i)
  if(sum(x)%i==0):
   m = sum(x)//i
   #print(m,i)
   break
 y = [max(0,m - a) for a in x]
 print(min(sum(sorted(z)),sum(sorted(y)[0:i])))
 
 
  
 
  


for t in range(int(input())):
 s = input()
 l = sorted([char for char in s])
 i = 0; x =[] 
 cnt = 1
 while(i<len(l)-1):
  if(l[i]!=l[i+1]):
   x.append(cnt)
   cnt = 0
  cnt = cnt+1
  i = i+1
 x.append(cnt) 
 #print(l,"\n",x)
 
 k = len(x)
 while(sum(x)%k!=0):
  k = k+1 
 m = sum(x)//k
 z = [max(0,a - m) for a in x]
   
 for i in range(len(x),0,-1):
  #print(sum(x),i)
  if(sum(x)%i==0):
   m = sum(x)//i
   #print(m,i)
   break
 y = [max(0,m - a) for a in x]
 print(min(sum(sorted(z)),sum(sorted(y)[0:i])))
 
 
  
 
  


T=int(input())
while(T>0):
 S=input()
 ls=[0 for i in range(26)]
 for x in S:
  ls[ord(x)-65]+=1
 n=len(S)
 c=1
 ls.sort(reverse = True)
 while(c<=26):
  if(n%c != 0):
   c=c+1
   continue
  else:
   f=n//c
   i=0
   temp_min=0
   while(i<c and i<len(ls)):
    temp_min+=min(ls[i],f)
    i=i+1
   temp_min=n-temp_min 
   if(c==1):
    minimum=temp_min
   else:
    if(minimum>temp_min):
     minimum=temp_min
  c=c+1
 print(minimum) 
 T=T-1 

t = int(input())
while t:
 s = input()
 n = len(s)
 res = n
 freq = [0]*26
 for i in s:
  freq[ord(i) - 65] += 1
 freq.sort(reverse = True)
 for i in range(1,27):
  if(n%i == 0):
   x = 0
   y = n//i
   for j in range(i):
    x += min(y, freq[j])
   res = min(n-x,res)
 print(res)
 t -= 1

for _ in range(int(input())):
 S=input()
 n=len(S)
 A=[0]*26
 for i in S:
  A[ord(i)-65]+=1
 A.sort()
 A=A[::-1]
 res=n
 for i in range(min(n,26)):
  if(n%(i+1)==0):
   F=n//(i+1)
   y=0
   for j in range(i+1):
    y+=min(A[j],F)
   res=min(res,n-y)
 print(res)


for _ in range(int(input())):
 S=input()
 n=len(S)
 A=[0]*26
 for i in S:
  A[ord(i)-65]+=1
 A.sort()
 A=A[::-1]
 res=n
 for i in range(26):
  if(n%(i+1)==0):
   F=n//(i+1)
   y=0
   for j in range(i+1):
    y+=min(A[j],F)
   res=min(res,n-y)
 print(res)


def solve_equal(lst,no_of_elem_in_group):
 dist = 0
 for i in lst:
  if i > no_of_elem_in_group:
   dist += abs(no_of_elem_in_group-i)
 return dist

def solve(lst,l,no_of_group):
 no_of_elem_in_group = l//no_of_group
 list_len = len(lst)
 dist = 0
 if no_of_group >= list_len:
  return solve_equal(lst,no_of_elem_in_group)

 else:  # no_of_group < list_len
  lst.sort()
  dist = sum(lst[0:list_len-no_of_group])
  return dist + solve_equal(lst,no_of_elem_in_group)

T = int(input())
for z in range(T):
 dct = {}
 s = list(input())
 for elem in s:
  try:
   dct[elem] += 1
  except:
   dct[elem] = 1
   
 lst = list(dct.values())
 l = len(s)
 mn = 99999999999999999
 for i in range(1,min(l+1,27)):
  no_of_group = i
  if l%no_of_group == 0:
   lst2 = lst[:]
   tmp = solve(lst2,l,no_of_group)
   #print(i,tmp)
   if tmp < mn:
    mn = tmp
 print(mn)



for test_case in range(int(input())):
 S = str(input())
 N = len(S)
 A = [0] * 27
 for character in S:
  A[ord(character) - 65] = A[ord(character) - 65] + 1
 A.sort(reverse=True)
 minSwap = N
 for i in range(1, 27):
  if N % i == 0:
   temp = N // i
   tempSwap = 0
   for f in range(i):
    if temp > A[f]:
     tempSwap = tempSwap + temp - A[f]
   if tempSwap <= minSwap:
    minSwap = tempSwap
 if minSwap == N + 1:
  minSwap = 0
 print(minSwap)


t = int(input())
for i in range(t):
 s = input()
 d = {}
 min1 = len(s)+1
 for i in s:
  if i not in d:
   d[i] = 1
  else:
   d[i] += 1
 l = [[x,y] for x,y in d.items()]
 l.sort(key = lambda j: j[1],reverse = True)
 for i in range(1,27):
  f = len(s)//i
  c = 0
  if len(s)%i != 0:
   continue
  j = 0
  while j < i and j < len(l):
   if l[j][1] >= f:
    c += f
   else:
    c += l[j][1]
   j += 1
  c = len(s)-c
  if c<min1:
   min1 = c
 print(min1)

t = int(input())
for i in range(t):
 s = input()
 d = {}
 min1 = len(s)+1
 for i in s:
  if i not in d:
   d[i] = 1
  else:
   d[i] += 1
 l = [[x,y] for x,y in d.items()]
 l.sort(key = lambda j: j[1],reverse = True)
 for i in range(1,26):
  f = len(s)//i
  c = 0
  if len(s)%i != 0:
   continue
  j = 0
  while j < i and j < len(l):
   if l[j][1] >= f:
    c += f
   else:
    c += l[j][1]
   j += 1
  c = len(s)-c
  if c<min1:
   min1 = c
 print(min1)

t = int(input())
for _ in range(t):
 str = input()
 new_str = set(str)
 char_freq = []
 for i in new_str:
  char_freq.append(str.count(i))
 char_freq.sort(reverse=True)
 charachter = []
 frepuency = []
 for i in range(1,27):
  if len(str)%i == 0:
   charachter.append(i)
   frepuency.append(len(str)/i)
 operation = []
 for j in range(len(charachter)):
  p_operation = 0
  n_operation = 0
  for i in range(charachter[j]):
   freq = frepuency[j]
   try:
    t_operation = freq - char_freq[i]
    if t_operation > 0:
     p_operation += t_operation
    else:
     n_operation += t_operation
   except:
    break
  n_operation = abs(n_operation)
  operation.append(max(p_operation, n_operation))

 print(int(min(operation)))