"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: MEDIUM_HARD
Tags: Number theory

Data structures

Mathematics

String algorithms
Skill types: Data structures

Starter code:

Solutions:
from collections import Counter

def factors(n):
	p = min(n + 1, 27)
	return [[i, n // i] for i in range(1, p) if n % i == 0]

def balance(s, x, typ, count):
	l = len(x)
	if l == typ:
		y = [i - count for i in x]
		y = [_ for _ in y if _ > 0]
		return sum(y)
	if l < typ:
		d = typ - l
		x.extend([0] * d)
		return balance(s, x, typ, count)
	if l > typ:
		y = sum(x[typ:])
		z = 0
		m = typ - 1
		while y:
			n = count - x[m]
			if n <= y:
				y -= n
			else:
				n = y
				y = 0
			z += n
			x[m] = x[m] + n
			m -= 1
		return z + balance(s, x[:typ], typ, count)
for t in range(int(input())):
	s = input()
	l = len(s)
	c = Counter(s)
	x = sorted(c.values())[::-1]
	r = [balance(s, x[:], typ, count) for (typ, count) in factors(l)]
	print(min(r))


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)


num = int(input())
for k in range(0, num):
	s = input()
	m = len(s)
	l = []
	c = 0
	if 1 == 1:
		for i in range(1, m + 1):
			if m % i == 0:
				if i > 26:
					break
				l.append(i)
		se = set(s)
		l1 = [0] * 26
		for i in s:
			l1[ord(i) - 65] += 1
		l1.sort()
		l1 = l1[::-1]
		l3 = []
		for i in range(len(l)):
			s = 0
			sum1 = 0
			p = m // l[i]
			for j in range(l[i]):
				if l1[j] > p:
					s = s + l1[j] - p
					sum1 = sum1 + l1[j] - p
				elif l1[j] < p:
					y = p - l1[j]
					if y < s:
						s = s - y
					else:
						sum1 += p - (s + l1[j])
						s = 0
			l3.append(sum1)
		if len(l3) == 0:
			print(sum(l1) - max(l1))
		else:
			print(min(l3))


from collections import defaultdict

def factors(n):
	f = []
	for i in range(1, min(n + 1, 27)):
		if n % i == 0:
			f.append(i)
	return sorted(f)
t = int(input())
for i in range(t):
	s = input()
	l = set(s)
	n = len(s)
	m = len(l)
	d = defaultdict(int)
	for i in s:
		d[i] += 1
	if max(d.values()) == min(d.values()):
		print(0)
	else:
		f = factors(n)
		sdv = sorted(d.values())
		counts = []
		for i in range(len(f)):
			lneeded = f[i]
			lcount = n // lneeded
			above = 0
			below = 0
			lnum = 0
			for j in range(len(sdv) - 1, -1, -1):
				if sdv[j] >= lcount:
					above += sdv[j] - lcount
					lnum += 1
				else:
					below += lcount - sdv[j]
					lnum += 1
				if lnum == lneeded:
					break
			counts.append(max(above, below))
		print(min(counts))


import sys

def count(str):
	le = len(str)
	dc = 26
	max = 0
	if le <= 2:
		return 0
	my_list = frequency(str)
	m = len(my_list)
	if le < dc:
		max = le
	else:
		max = dc
	sm = sys.maxsize - 1
	for i in range(1, max + 1):
		if le % i == 0:
			mov = moves(le, my_list, m, i)
			if mov < sm:
				sm = mov
	return sm

def frequency(str):
	my_list = [0] * 26
	for x in str:
		my_list[ord(x) - 65] += 1
	my_list.sort(reverse=True)
	k = 0
	for x in my_list:
		k += 1
		if x == 0:
			break
	return my_list[:k + 1]

def moves(le, freq, m, n):
	avg = le / n
	mov = 0
	if n == m:
		for x in freq:
			if x <= avg:
				break
			mov += x - avg
	elif n < m:
		for i in range(n):
			mov += abs(freq[i] - avg)
		for i in range(n, m, 1):
			mov += freq[i]
		mov = int(mov)
		mov >>= 1
	else:
		for i in range(len(freq)):
			mov += abs(freq[i] - avg)
		mov += (n - m) * avg
		mov = int(mov)
		mov >>= 1
	return mov
t = int(input())
while t != 0:
	k = input()
	print(int(count(k)))
	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)


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


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)


for _ in range(int(input())):
	n = list(input())
	d = {}
	lenth = len(n)
	for i in n:
		if d.get(i) == None:
			d[i] = 1
		else:
			d[i] = d[i] + 1
	l = []
	for k in d:
		l.append(d[k])
	l.sort(reverse=True)
	while len(l) < 26:
		l.append(0)
	result = 1000006
	for k in range(1, 27):
		sm = 1
		if lenth % k == 0:
			tem = lenth // k
			for j in range(0, k):
				sm = sm + abs(l[j] - tem)
			for b in range(k, 26):
				sm = sm + l[b]
			sm = sm // 2
			result = min(result, sm)
	print(result)


t = int(input())
for u in range(t):
	s = input()
	n = len(s)
	nodc = len(set(s))
	freq = [0] * 27
	for j in range(0, n):
		freq[ord(s[j]) - ord('A')] += 1
	freq = sorted(freq, reverse=True)
	mn = n + 1
	for i in range(1, 27):
		if n % i == 0:
			gl = n // i
			sm = 0
			for j in range(i):
				if gl > freq[j]:
					sm += gl - freq[j]
			if sm <= mn:
				mn = sm
	if mn == n + 1:
		mn = 0
	print(mn)


for _ in range(int(input())):
	s = input()
	a = [0] * 27
	for i in s:
		a[ord(i) - ord('A')] += 1
	a.sort(reverse=True)
	b = []
	for i in range(1, len(s) // 2 + 1):
		if len(s) % i == 0:
			(j, c, l) = (0, 0, 0)
			while l < len(s) and j < 27:
				if i - a[j] > 0:
					c += i - a[j]
				l += i
				j += 1
			if j < 27:
				b.append(c)
	b.append(len(s) - max(a))
	print(min(b))


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)


for _ in range(int(input())):
	ip = list(input())
	n = len(ip)
	freq = [0] * 26
	for i in range(n):
		freq[ord(ip[i]) - ord('A')] += 1
	freq.sort()
	ans = 99999999999999999
	for i in range(1, 27):
		if n % i != 0:
			continue
		bal_no = n / i
		(total, repetition) = (0, 0)
		for j in range(1, i + 1):
			total += abs(freq[26 - j] - bal_no)
			repetition += freq[26 - j]
		ans = min((n - repetition + total) / 2, ans)
	print(int(ans))


t = int(input())
for ia in range(t):
	s = input()
	l = [0] * 26
	for i in s:
		l[ord(i) - ord('A')] += 1
	l.sort(reverse=True)
	n = len(s)
	ma = 999999999999
	for i in range(1, 27):
		p = []
		if n % i == 0:
			ans = 0
			for j in range(i):
				p.append(n // i)
			for k in range(26 - i):
				p.append(0)
			for z in range(len(p)):
				ans += abs(p[z] - l[z])
			if ans < ma:
				ma = ans
	print(ma // 2)


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


t = int(input())
while t > 0:
	numberOfEachLetter = []
	stringGCD = []
	hashMap = {}
	z = []
	string1 = input()
	lengthOfString = len(string1)
	for i in string1:
		if i in hashMap:
			hashMap[i] += 1
		else:
			hashMap[i] = 1
	diffL = len(hashMap)
	if diffL == 0:
		print(0)
		continue
	for i in hashMap:
		numberOfEachLetter.append(hashMap[i])
	numberOfEachLetter.sort(reverse=True)
	for i in range(1, 27):
		if lengthOfString % i == 0 and i <= lengthOfString:
			stringGCD.append(i)
	for j in stringGCD:
		diffL = len(numberOfEachLetter)
		fDf = 0
		rmL = 0
		newLetters = 0
		stringIndex = len(numberOfEachLetter) - 1
		equalFrequency = lengthOfString // j
		while diffL > j:
			rmL += numberOfEachLetter[stringIndex]
			stringIndex -= 1
			diffL -= 1
		while j > diffL:
			newLetters += equalFrequency
			j -= 1
		while stringIndex >= 0:
			fDf += abs(numberOfEachLetter[stringIndex] - equalFrequency)
			stringIndex -= 1
		singleAns = (fDf + rmL + newLetters) // 2
		z.append(singleAns)
	print(min(z))
	t -= 1


t = int(input())
for T in range(t):
	st = input()
	l = [0] * 26
	for i in st:
		l[ord(i) - 65] += 1
	l[:] = (value for value in l if value != 0)
	l.sort()
	l2 = []
	for i in range(26, 0, -1):
		sum_ = 0
		if len(st) % i == 0:
			if i > len(l):
				max_ = len(st) / i
				for j in range(len(l) - 1, -1, -1):
					if l[j] - max_ > 0:
						sum_ += l[j] - max_
					else:
						break
				l2.append(int(sum_))
			elif i == len(l):
				max_ = len(st) / i
				for j in range(len(l)):
					if l[j] - max_ > 0:
						sum_ += l[j] - max_
				l2.append(int(sum_))
			else:
				cum = 0
				max_ = len(st) / i
				for j in range(len(l) - i):
					cum += l[j]
				for j in range(len(l) - 1, -1, -1):
					if l[j] > max_:
						cum += l[j] - max_
					else:
						break
				l2.append(int(cum))
	print(min(l2))


from collections import Counter
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	freq = Counter(s)
	ans = float('inf')
	values = list(freq.values())
	values.sort(reverse=True)
	for i in range(1, 27):
		distinct = i
		if n % i == 0:
			goal = n // i
			same = 0
			trim = values[:distinct]
			for c in trim:
				if c > goal:
					same += goal
				else:
					same += c
			left = n - same
			ans = min(ans, left)
	print(ans)


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
			elif minimum > temp_min:
				minimum = temp_min
		c = c + 1
	print(minimum)
	T = T - 1


from collections import Counter
import math
import os
import random
import re
import sys
for a0 in range(int(input())):
	st = input()
	c = Counter(st)
	n = len(st)
	m = len(c.keys())
	ans = 10000000000
	l = []
	for i in range(65, 91):
		l.append([chr(i), c.get(chr(i), 0)])
	l = sorted(l, key=lambda l: l[1], reverse=True)
	for i in range(1, 27):
		a = []
		s = 0
		if n % i == 0:
			t = n // i
			for j in l:
				if j[1] >= t:
					a.append(j[1] - t)
					s += j[1] - t
				elif t - j[1] >= s:
					a.append(t - j[1] - s)
					s = 0
				else:
					s -= t - j[1]
					a.append(0)
			ans = min(ans, sum(a[:i]))
	print(ans)


t = int(input())
mod = lambda a, b: int(a - b) if a > b else int(b - a)
while t:
	l = list(input().strip())
	alpha_c = len(set(l))
	n = 26 if len(l) > 26 else len(l)
	dicti = {}
	for ele in l:
		dicti[ele] = dicti[ele] + 1 if dicti.get(ele) != None else 1
	vals = list(dicti.values())
	for lv in range(n - alpha_c):
		vals.append(0)
	vals.sort()
	ans = 0
	count = 0
	if n == 1:
		print(0)
	else:
		for i in range(n, 0, -1):
			if len(l) % i:
				continue
			occ = len(l) // i
			count += 1
			su = 0
			for lv in range(n - i):
				su += mod(vals[lv], 0)
			for lv in range(n - i, n):
				su += mod(vals[lv], occ)
			if count == 1:
				ans = su
			elif su < ans:
				ans = su
		print(ans // 2)
	t -= 1


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


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


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:
		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)
			if tmp < mn:
				mn = tmp
	print(mn)


t = int(input())
for x in range(t):
	s = input()
	l = []
	fac = []
	c = []
	for x in range(26):
		l.append(0)
	for x in s:
		p = ord(x) - 65
		l[p] = l[p] + 1
	l.sort()
	v = 26 - l.count(0)
	for x in range(1, len(s) + 1):
		if len(s) % x == 0:
			if len(s) // x < 27:
				fac.append(len(s) // x)
	for x in range(len(fac)):
		cc = 0
		if v < fac[x]:
			for y in range(l.count(0), 26):
				if l[y] > len(s) // fac[x]:
					cc = cc + l[y] - len(s) // fac[x]
		else:
			for y in range(25, l.count(0) + (v - fac[x]) - 1, -1):
				if l[y] < len(s) // fac[x]:
					cc = cc + len(s) // fac[x] - l[y]
		c.append(cc)
	print(min(c))


MAX = 1000001

def fun(l, n):
	mn = 100000000000.0
	for f in range(1, 27):
		if f == 1:
			mn = min(mn, n - max(l))
		elif n % f == 0:
			k = n // f
			s = l[:f]
			c1 = 0
			c2 = 0
			for i in s:
				if i > k:
					c1 += i - k
			for i in l[f:]:
				c2 += i
			mn = min(mn, c1 + c2)
	return mn
t = int(input())
for i in range(t):
	s = input()
	l = []
	n = len(s)
	for i in set(s):
		l.append(s.count(i))
	l.sort(reverse=True)
	ans = fun(l, n)
	print(ans)


def fac(k):
	fa = []
	for i in range(1, k + 1):
		if k % i == 0:
			if i > 26:
				break
			fa.append(i)
	fa = list(set(fa))
	fa.sort()
	return fa
for _ in range(int(input())):
	s = input()
	l = [0] * 26
	for i in range(len(s)):
		l[ord(s[i]) - 65] += 1
	l.sort()
	l = l[::-1]
	k = sum(l)
	f = fac(k)
	ans = []
	for i in range(len(f)):
		l1 = l
		p = k // f[i]
		c = 0
		s = 0
		for j in range(f[i]):
			if l1[j] > p:
				s = s + l1[j] - p
				c = c + l1[j] - p
			elif l1[j] < p:
				y = p - l1[j]
				if y < s:
					s = s - y
				else:
					c += p - (s + l1[j])
					s = 0
		ans.append(c)
	if len(ans) == 0:
		print(k - max(l))
	else:
		print(min(ans))


for _ in range(int(input())):
	s = input()
	a = [0] * (26 - len(set(s)))
	b = []
	c = []
	d = []
	for i in s:
		if i not in b:
			b.append(i)
			a.append(s.count(i))
	a.sort(reverse=True)
	if len(list(set(s))) == len(s):
		print('0')
	else:
		n = len(s)
		for i in range(1, 27):
			if n % i == 0:
				c.append(i)
		for i in c:
			v = 0
			for j in range(0, i):
				if int(n / i) - a[j] > 0:
					v = v + (int(n / i) - a[j])
			d.append(v)
		print(min(d))


for _ in range(int(input())):
	l = input()
	l1 = len(l)
	count = [0] * 27
	for x in range(l1):
		co = ord(l[x]) - 65
		count[co] += 1
	count.sort(reverse=True)
	minim = 1000000000
	for x in range(1, 27):
		if l1 % x == 0:
			ste = 0
			ave = l1 // x
			for x2 in range(x):
				if ave > count[x2]:
					ste += ave - count[x2]
			if minim > ste:
				minim = ste
	if minim == l1 + 1:
		minim = 0
	print(minim)


def hash_it(arr, s):
	for i in range(len(s)):
		arr[ord(s[i]) - 65] += 1
	arr = sorted(arr, reverse=True)
	return arr

def balance(s, arr, l):
	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())):
	s = input()
	l = len(s)
	if l <= 2:
		print(0)
		continue
	arr = [0 for i in range(0, 27)]
	arr = hash_it(arr, s)
	print(balance(s, arr, l))


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)
	m = 0
	for k in range(len(x), 27):
		if sum(x) % k == 0:
			m = sum(x) // k
			break
	z = [max(0, a - m) for a in x]
	for i in range(len(x), 0, -1):
		if sum(x) % i == 0:
			m = sum(x) // i
			break
	y = [max(0, m - a) for a in x]
	print(min(sum(sorted(z)), sum(sorted(y)[0:i])))


t = int(input())
for j in range(t):
	n = input()
	l = len(n)
	a = [0] * 26
	b = list(set(n))
	for i in b:
		a[ord(i) - 65] = n.count(i)
	a.sort(reverse=True)
	inc = 0
	m = 10000000
	for i in range(26, 0, -1):
		inc = 0
		if l % i == 0:
			p = l // i
			for k in range(0, i):
				if a[k] < p:
					inc = inc + p - a[k]
			m = min(m, inc)
	print(m)


from collections import defaultdict as dd
for i in range(int(input())):
	S = list(str(input()))
	v = dd(int)
	for i in range(len(S)):
		v[S[i]] += 1
	l = list(v.values())
	l.sort(reverse=True)
	z = sum(l)
	req1 = len(S) - len(set(S))
	req2 = len(S) - max(l)
	if len(S) <= 26:
		m1 = min(req1, req2)
	else:
		m1 = req2
	for i in range(2, int(z / 2) + 1):
		k = 0
		c = 0
		if z % i == 0 and int(z / i) <= 26:
			n = int(z / i)
			k = 1
			if n > len(l):
				c += (n - len(l)) * i
				for j in range(len(l)):
					if i - l[j] > 0:
						c += i - l[j]
			else:
				for j in range(n):
					if i - l[j] > 0:
						c += i - l[j]
		if c < m1 and k == 1:
			m1 = c
	print(m1)


import collections
from functools import reduce

def factors(n):
	x = set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
	return list(x)
testcase = int(input())
for k in range(testcase):
	l = []
	string = input()
	list1 = [i for i in string]
	length = len(list1)
	freq = [0] * 26
	list2 = {i for i in string}
	for j in string:
		freq[ord(j) - ord('A')] += 1
	freq.sort(reverse=True)
	for i in range(1, 27):
		count = 0
		if len(list1) % i == 0:
			for k in range(min(i, len(list2))):
				count += min(freq[k], length / i)
			l.append(abs(count - length))
	print(int(min(l)))


r = []
for i in range(int(input())):
	s = input()
	d = {}
	l = []
	for i in s:
		if i in d:
			d[i] += 1
			continue
		d[i] = 1
	for i in d:
		l.append(d[i])
	l.sort()
	n = len(s)
	p = []
	for i in range(1, 1 + 26):
		a = 0
		if n % i == 0:
			if i > len(l):
				while i != len(l):
					l = [0] + l
			k = n // i
			bal_l = [k for _ in range(i)]
			while len(bal_l) != len(l):
				bal_l = [0] + bal_l
			for z in range(len(l)):
				a += abs(l[z] - bal_l[z])
			p += [a // 2]
	r += [min(p)]
for i in r:
	print(i)


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	T = int(input())
	for _ in range(T):
		s = input()
		count = dict()
		for char in s:
			if char in count:
				count[char] += 1
			else:
				count[char] = 1
		values = sorted(count.values(), reverse=True)
		N = len(s)
		res = []
		for i in range(1, min(N, 26) + 1):
			if N % i == 0:
				total = 0
				above = 0
				below = 0
				for j in range(min(len(values), i)):
					if N // i - values[j] > 0:
						above += N // i - values[j]
					else:
						below += abs(N // i - values[j])
				if below == 0:
					total = above
				elif above == 0:
					total = below
				else:
					total = max(above, below)
				res.append(total)
		print(min(res))
main()


from string import ascii_uppercase as au
alpha_val = dict(zip(au, list(range(1, 27))))
nb_test = int(input())
for _ in range(nb_test):
	curr = input()
	lens = len(curr)
	alpha = [0] * 27
	for i in curr:
		alpha[alpha_val[i]] += 1
	alpha = sorted(alpha, reverse=True)
	mins = lens + 1
	for i in range(1, 27):
		if lens % i == 0:
			this = lens // i
			will = 0
			for f in range(i):
				if this > alpha[f]:
					will += this - alpha[f]
			if will <= mins:
				mins = will
	print([mins, 0][mins == lens + 1])


try:
	for i in range(int(input())):
		string = str(input())
		n = len(string)
		ans = [0] * 27
		for char in string:
			ans[ord(char) - 65] += 1
		ans = sorted(ans, reverse=True)
		minSwap = n + 1
		for j in range(1, 27):
			if n % j == 0:
				temp = n // j
				tempSwap = 0
				for f in range(j):
					if temp > ans[f]:
						tempSwap = tempSwap + temp - ans[f]
				if tempSwap <= minSwap:
					minSwap = tempSwap
		if minSwap == n + 1:
			minSwap = 0
		print(minSwap)
except:
	print('asda')


for _ in range(int(input())):
	s = list(input())
	s_set = {}
	for x in s:
		if x in s_set:
			s_set[x] += 1
		else:
			s_set[x] = 1
	result = []
	nums = [_ for _ in s_set.values()]
	nums.sort(reverse=True)
	nums = list(nums + [0] * (26 - len(nums)))
	for i in range(26, 0, -1):
		if len(s) % i == 0:
			nums_cut = nums[:i]
			cout = 0
			t = len(s) // i
			for x in nums_cut:
				if x < t:
					cout += t - x
			result.append(cout)
	print(min(result))


for j in range(int(input())):
	S = str(input())
	N = len(S)
	A = [0] * 27
	for c in S:
		A[ord(c) - 65] = A[ord(c) - 65] + 1
	A = sorted(A, reverse=True)
	minSwap = N + 1
	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)


import sys
R = lambda : 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)


t = ''
try:
	t = int(input())
except:
	pass
while t:
	t = t - 1
	S = input()
	N = len(S)
	A = [0] * 27
	for c in S:
		A[ord(c) - 65] = A[ord(c) - 65] + 1
	A = sorted(A, reverse=True)
	minSwap = N + 1
	for i in range(1, 27):
		if N % i == 0:
			temp1 = N // i
			tempSwap = 0
			for f in range(i):
				if temp1 > A[f]:
					tempSwap = tempSwap + temp1 - A[f]
			if tempSwap <= minSwap:
				minSwap = tempSwap
	if minSwap == N + 1:
		minSwap = 0
	print(minSwap)


from sys import stdin
import math
from functools import reduce

def defactors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def factors(n, min):
	alpha = set()
	bin = defactors(n)
	for i in bin:
		if i >= min:
			alpha.add(i)
	return alpha

def dervel(array, fact, length):
	sum = 0
	for i in range(int(length / fact)):
		if array[i] < fact:
			sum = sum + array[i] - fact
	return -sum
test = int(input())
for trouble in range(test):
	s = input()
	length = len(s)
	x = [0 for i in range(26)]
	for c in s:
		x[ord(c) - 65] += 1
	x.sort()
	x.reverse()
	min = math.ceil(length / 26)
	factor = list(factors(length, min))
	factarr = [0 for i in range(len(factor))]
	for i in range(0, len(factor)):
		factarr[i] = dervel(x, factor[i], length)
	factarr.sort()
	print(factarr[0])


T = int(input())
while T > 0:
	T = T - 1
	string1 = input()
	lengthOfString = len(string1)
	mapOfLetters = {}
	answerList = []
	numberOfEachLetter = []
	stringGCD = []
	for i in string1:
		if i in mapOfLetters:
			mapOfLetters[i] += 1
		else:
			mapOfLetters[i] = 1
	differentLetters = len(mapOfLetters)
	if differentLetters == 0:
		print(0)
		continue
	for i in mapOfLetters:
		numberOfEachLetter.append(mapOfLetters[i])
	numberOfEachLetter.sort(reverse=True)
	for i in range(1, 27):
		if lengthOfString % i == 0 and i <= lengthOfString:
			stringGCD.append(i)
	for j in stringGCD:
		differentLetters = len(numberOfEachLetter)
		frequencyDifference = 0
		removedLetters = 0
		newLetters = 0
		stringIndex = len(numberOfEachLetter) - 1
		equalFrequency = lengthOfString // j
		while differentLetters > j:
			removedLetters += numberOfEachLetter[stringIndex]
			stringIndex -= 1
			differentLetters -= 1
		while j > differentLetters:
			newLetters += equalFrequency
			j -= 1
		while stringIndex >= 0:
			frequencyDifference += abs(numberOfEachLetter[stringIndex] - equalFrequency)
			stringIndex -= 1
		singleAns = (frequencyDifference + removedLetters + newLetters) // 2
		answerList.append(singleAns)
	print(min(answerList))


t = int(input())
while t > 0:
	l1 = []
	s = input()
	s1 = list(set(s))
	for i in range(0, 26):
		x = s.count(chr(i + 65))
		l1.append(x)
	l1.sort()
	m = len(l1)
	n = len(s)
	mi = 1000001
	for i in range(1, 27):
		k = 0
		r = 0
		if n % i == 0:
			r = n // i
			j = m - 1
			while j > 25 - i:
				if r - l1[j] > 0:
					k = k + (r - l1[j])
				j = j - 1
			if mi > k:
				mi = k
	print(mi)
	t = t - 1


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


def Tee():
	chars = [0 for i in range(26)]
	S = input()
	for i in range(26):
		chars[i] = S.count(chr(65 + i))
	prev = -1
	sumi = len(S)
	chars.sort(reverse=True)
	for i in range(1, 27):
		positive_temp = 0
		if sumi % i == 0:
			store = sumi // i
			for j in range(i):
				if store - chars[j] > 0:
					positive_temp += store - chars[j]
			if prev == -1:
				prev = positive_temp
			elif prev > positive_temp:
				prev = positive_temp
	print(max(prev, 0))
for i in range(int(input())):
	Tee()


def check(avg, sortedflag, c):
	count1 = count2 = 0
	for i in range(len(sortedflag)):
		if sortedflag[i] != 0 and i < c:
			if sortedflag[i] > avg:
				count1 += sortedflag[i] - avg
			else:
				count2 += avg - sortedflag[i]
	if count1 > count2:
		return count1
	else:
		return count2
t = int(input())
for _ in range(t):
	flag = [0 for x in range(26)]
	s = input()
	l = len(s)
	c = 0
	result1 = result2 = 10000000
	for i in s:
		if flag[ord(i) - 65] == 0:
			c += 1
		flag[ord(i) - 65] += 1
	sortedflag = sorted(flag, reverse=True)
	avg = l // c
	avg1 = avg2 = avg
	r = l % c
	r1 = r2 = r
	c1 = c2 = c
	while r1 != 0:
		c1 -= 1
		avg1 = l // c1
		r1 = l % c1
	while r2 != 0:
		c2 += 1
		avg2 = l // c2
		r2 = l % c2
	result1 = check(avg1, sortedflag, c1)
	if c2 < 27:
		result2 = check(avg2, sortedflag, c2)
	if result1 < result2:
		print(result1)
	else:
		print(result2)


from collections import Counter
import operator

def print_factors(x):
	l = []
	for i in range(1, x + 1):
		if x % i == 0:
			l.append(i)
	return l
t = int(input())
for i in range(t):
	s = list(input())
	fac = print_factors(len(s))
	res = Counter(s)
	values = []
	for q in res.values():
		values.append(q)
	flag = 0
	h = len(s)
	if len(fac) == 2 and h > 26:
		print(h - max(values))
	else:
		cl = []
		y = h // 26
		if h % 26 == 0:
			y = y - 1
		for e in range(1, y + 1):
			if e in fac:
				fac.remove(e)
		for j in fac:
			tot = 0
			(maxi, mini) = (0, 0)
			x = min(len(values), h // j)
			values.sort()
			values.reverse()
			for he in range(x):
				if values[he] > j:
					maxi += values[he] - j
				else:
					mini += j - values[he]
			cl.append(max(mini, maxi))
		print(min(cl))


def solve(arr, n):
	least = n
	for c in range(1, 27):
		if n % c == 0:
			tot = 0
			f = int(n / c)
			for i in range(len(arr)):
				if arr[i] > f:
					tot += abs(arr[i] - f)
				elif i >= c:
					tot += arr[i]
			if tot < least:
				least = tot
	print(least)
for _ in range(int(input())):
	arr = [0] * 26
	s = input()
	n = 0
	for ch in s:
		arr[ord(ch) - 65] += 1
		n += 1
	arr.sort(reverse=True)
	for i in range(26):
		if arr[i] == 0:
			arr = arr[:i]
			break
	solve(arr, n)


for _ in range(int(input())):
	subodh = str(input())
	arr = [0 for x in range(26)]
	for i in subodh:
		alpha = ord(i) - 65
		arr[alpha] += 1
	arr.sort()
	Minimum = 10000000
	for i in range(1, 27):
		Temp = 0
		if len(subodh) % i == 0:
			repeat = len(subodh) // i
			for j in range(26 - i, 26, 1):
				if arr[j] < repeat:
					Temp1 = repeat - arr[j]
					Temp = Temp + Temp1
			if Temp < Minimum:
				Minimum = Temp
	print(Minimum)


for i in range(int(input())):
	s = list(input())
	array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for index in s:
		k_index = ord(index) - 65
		array[k_index] = array[k_index] + 1
	array.sort()
	counter = 0
	minimum = 2147483647
	flagBool = False
	for j in range(1, len(s) + 1):
		if minimum == 0:
			break
		elif len(s) % j == 0:
			for k_index in range(j, 0, -1):
				if k_index <= len(array) and array[len(array) - k_index] <= len(s) / j:
					counter = counter + len(s) / j - array[len(array) - k_index]
					flagBool = True
				else:
					break
			if counter < minimum and flagBool == True:
				minimum = counter
				counter = 0
				flagBool = False
		else:
			continue
	print(int(minimum))


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


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	y = 2000009
	p = []
	i = 0
	while i < 26:
		p.append(s.count(chr(i + 65)))
		i = i + 1
	p.sort()
	i = 1
	while i < 27:
		if n / i == 0:
			break
		x1 = 0
		if n % i == 0:
			r = n // i
			for j in range(25, 25 - i, -1):
				if r - p[j] > 0:
					z = r - p[j]
					x1 = x1 + z
			if y > x1:
				y = x1
		i = i + 1
	print(y)
	t = t - 1


from collections import Counter
test = int(input())
for x in range(test):
	s = input()
	n = len(s)
	counter = Counter(s)
	count = []
	for i in counter.items():
		count.append(i[1])
	count.sort(reverse=True)
	ans = n
	for i in range(1, min(n, 26) + 1):
		if n % i == 0:
			k = n // i
			mid1 = 0
			mid2 = 0
			for j in range(min(i, len(count))):
				if k > count[j]:
					mid1 += k - count[j]
				elif k < count[j]:
					mid2 -= k - count[j]
		ans = min(ans, max(mid1, mid2))
	print(ans)


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)


t = int(input())
for i in range(t):
	word = input()
	Alphabet = ['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']
	a = []
	dif = 0
	for i in range(0, 26):
		b = word.count(Alphabet[i])
		if b != 0:
			dif = dif + 1
			a.append(b)
	a.sort()
	length = len(word)
	diff = 1
	for i in range(dif, 0, -1):
		if length % i == 0:
			balno = length // i
			remove = dif - i
			break
	ans = 0
	for i in range(0, dif):
		if i < remove:
			ans += a[i]
		elif a[i] != 0:
			if a[i] > balno:
				ans += a[i] - balno
	temp = 0
	for i in range(dif + 1, 27):
		if length % i == 0:
			balno = length // i
			for j in range(0, dif):
				if balno < a[j]:
					temp += a[j] - balno
			if temp < ans:
				ans = temp
	print(ans)


for testc in range(int(input())):
	s = input()
	a = [0 for x in range(26)]
	for char in s:
		a[ord(char) - 65] += 1
	i = 0
	a.sort(reverse=True)
	su = sum(a)
	t = 0
	x = 0
	while t < 26:
		if a[t] is not 0:
			x += 1
		t += 1
	ans = su - a[0]
	l = len(s)
	for i in range(2, min(26, l) + 1, 1):
		if l % i == 0:
			avg = int(l / i)
			tmp = 0
			if i > x:
				j = 0
				while a[j] > avg:
					tmp += a[j] - avg
					j += 1
			else:
				k = 0
				extra = 0
				while a[k] > avg:
					extra += a[k] - avg
					k += 1
				k = i
				rest = 0
				while k < 26:
					rest += a[k]
					k += 1
				tmp = extra + rest
			if tmp < ans:
				ans = tmp
	print(ans)


import math
n = int(input())
while n > 0:
	s = input()
	l = len(s)
	a = [0] * 100
	c = []
	d = []
	maximum = 10000000000000
	for i in range(0, l):
		b = ord(s[i])
		a[b] = a[b] + 1
	for i in range(65, 91):
		if a[i] > 0:
			c.append(a[i])
	j = len(c)
	c = sorted(c)[::-1]
	z = int(math.sqrt(l))
	for i in range(1, z + 1):
		if l % i == 0:
			if l // i == i:
				d.append(i)
			else:
				d.append(i)
				d.append(l // i)
	x = len(d)
	for i in range(0, x):
		if l // d[i] > 26:
			continue
		if l > 26 and d[i] == 1 and (j == 26):
			continue
		p = 0
		q = 0
		k = 0
		w = 0
		for k in range(0, j):
			if d[i] - c[k] > 0:
				p = p + d[i] - c[k]
			q = q + d[i]
			if q >= l:
				break
		if q < l:
			w = l - (k + 1) * d[i]
			p = p + w
		if p < maximum:
			maximum = p
	print(maximum)
	n = n - 1


t = int(input())
for i in range(t):
	s = input()
	a = [0 for x in range(26)]
	L = []
	list1 = []
	for j in range(len(s)):
		a[ord(s[j]) - ord('A')] += 1
	for x in a:
		if x != 0:
			L.append(x)
	sum = 0
	N = len(s)
	y = 0
	L.sort()
	a.sort()
	if L[0] == L[-1]:
		print(0)
	else:
		for k in range(len(a), 0, -1):
			if N % k == 0:
				param = N // k
				for z in range(y):
					sum += a[z]
				for p in range(len(a) - 1, y - 1, -1):
					if a[p] > param:
						sum += a[p] - param
				if sum != 0:
					list1.append(sum)
				sum = 0
			y += 1
		list1.sort()
		print(list1[0])


t = int(input())
for i in range(0, t):
	mini = 99999999999999
	s = input()
	length = len(s)
	dict1 = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
	for j in range(0, len(s)):
		dict1[s[j].lower()] += 1
	a = []
	for j in dict1:
		if dict1[j] > 0:
			a.append(dict1[j])
	a.sort(reverse=True)
	lenarr = len(a)
	for j in range(0, 26 - lenarr):
		a.append(0)
	for k in range(1, 27):
		if length % k == 0:
			avg = length // k
			count = 0
			for j in range(0, k, 1):
				if a[j] < avg:
					count += avg - a[j]
					print
			if count < mini:
				mini = count
	print(mini)


T = int(input())
while T > 0:
	T = T - 1
	string1 = input()
	lengthOfString = len(string1)
	mapOfLetters = {}
	potentialAnswer = []
	for i in string1:
		if i in mapOfLetters:
			mapOfLetters[i] += 1
		else:
			mapOfLetters[i] = 1
	differentLetters = len(mapOfLetters)
	if differentLetters == 0:
		print(0)
		continue
	numberOfEachLetter = []
	for i in mapOfLetters:
		numberOfEachLetter.append(mapOfLetters[i])
	numberOfEachLetter.sort(reverse=True)
	divisorsOfStringLength = []
	for i in range(1, 27):
		if lengthOfString % i == 0 and i <= lengthOfString:
			divisorsOfStringLength.append(i)
	for j in divisorsOfStringLength:
		differentLetters = len(numberOfEachLetter)
		k1 = 0
		k2 = 0
		pseudoLength = len(numberOfEachLetter) - 1
		distribution = lengthOfString // j
		while differentLetters > j:
			k2 += numberOfEachLetter[pseudoLength]
			pseudoLength -= 1
			differentLetters -= 1
		j2 = j
		corrector = 0
		while j2 > differentLetters:
			corrector += distribution
			j2 -= 1
		while pseudoLength >= 0:
			k1 += abs(numberOfEachLetter[pseudoLength] - distribution)
			pseudoLength -= 1
		p = (k1 + k2 + corrector) // 2
		potentialAnswer.append(p)
	print(min(potentialAnswer))


T = int(input())
while T > 0:
	T = T - 1
	s = input()
	total = len(s)
	x = {}
	z = []
	maxL = 0
	for i in s:
		if i in x:
			x[i] += 1
		else:
			x[i] = 1
	variations = len(x)
	if variations == 0:
		print(0)
		continue
	y = []
	for i in x:
		y.append(x[i])
	y.sort(reverse=True)
	z2 = []
	for i in range(1, 27):
		if total % i == 0 and i <= total:
			z2.append(i)
	for j in z2:
		variations = len(y)
		i = 1
		k1 = 0
		k2 = 0
		pseudoLength = len(y) - 1
		distribution = total // j
		while variations > j:
			k2 += y[pseudoLength]
			pseudoLength -= 1
			variations -= 1
		j2 = j
		corrector = 0
		while j2 > variations:
			corrector += distribution
			j2 -= 1
		while pseudoLength >= 0:
			k1 += abs(y[pseudoLength] - distribution)
			pseudoLength -= 1
		p = (k1 + k2 + corrector) // 2
		z.append(p)
	print(min(z))


from collections import Counter
for _ in range(int(input())):
	s = input()
	f = Counter(s)
	n = len(s)
	ans = float('inf')
	values = list(f.values())
	values.sort(reverse=True)
	for i in range(1, 27):
		d = i
		if n % i == 0:
			g = n // i
			s = 0
			trim = values[:d]
			for j in trim:
				if j > g:
					s += g
				else:
					s += j
			ans = min(ans, n - s)
	print(ans)


import string
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	c = {x: 0 for x in string.ascii_uppercase}
	for char in s:
		c[char] += 1
	c = {k: v for (k, v) in c.items() if v > 0}
	c = sorted(c.items(), key=lambda item: item[1])
	l = len(c)
	min_cnt = 10 ** 9
	for i in range(1, 27):
		if not n % i == 0:
			continue
		each_cnt = n // i
		req = 0
		if i < l:
			j = 1
			for (k, v) in reversed(c):
				if j > i:
					break
				if v > each_cnt:
					req += v - each_cnt
				j += 1
			for (k, v) in c:
				if j > l:
					break
				req += v
				j += 1
		else:
			for (k, v) in c:
				if v > each_cnt:
					req += v - each_cnt
		min_cnt = min(min_cnt, req)
	print(min_cnt)