Chef Al Gorithm was reading a book about climate and oceans when he encountered the word “glaciological”. He thought it was quite curious, because it has the following interesting property: For every two letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ 1.
Chef Al was happy about this and called such words 1-good words. He also generalized the concept: He said a word was K-good if for every two letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ K.
Now, the Chef likes K-good words a lot and so was wondering: Given some word w, how many letters does he have to remove to make it K-good?

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of a single line containing two things: a word w and an integer K, separated by a space.

-----Output-----
For each test case, output a single line containing a single integer: the minimum number of letters he has to remove to make the word K-good.

-----Constraints-----
- 1 ≤ T ≤ 30
- 1 ≤ |w| ≤ 105
- 0 ≤ K ≤ 105
- w contains only lowercase English letters.

-----Example-----
Input:
4
glaciological 1
teammate 0
possessions 3
defenselessness 3

Output:
0
0
1
2

-----Explanation-----
Example case 1. The word “glaciological” is already 1-good, so the Chef doesn't have to remove any letter.
Example case 2. Similarly, “teammate” is already 0-good.
Example case 3. The word “possessions” is 4-good. To make it 3-good, the Chef can remove the last s to make “possession”.
Example case 4. The word “defenselessness” is 4-good. To make it 3-good, Chef Al can remove an s and an e to make, for example, “defenslesness”. Note that the word doesn't have to be a valid English word.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import string
for _ in range(int(input())):
	(s, k) = list(map(str, input().split()))
	k = int(k)
	lower = [i for i in string.ascii_lowercase]
	l = {}
	for i in lower:
		l[i] = 0
	for i in s:
		l[i] += 1
	ans = len(s)
	for i in lower:
		c = 0
		for j in lower:
			if l[j] < l[i]:
				c += l[j]
			elif l[j] - l[i] > k:
				c += l[j] - l[i] - k
		ans = min(ans, c)
	print(ans)


t = int(input())
while t:
	(w, k) = input().split()
	k = int(k)
	char = {}
	for c in w:
		if c not in list(char.keys()):
			char[c] = 1
		else:
			char[c] += 1
	counts = list(char.values())
	counts.sort()
	l = len(counts)
	ans = len(w) + 1
	for i in range(l):
		temp = 0
		for j in range(l):
			if counts[j] < counts[i]:
				temp += counts[j]
			elif counts[j] > counts[i] + k:
				temp += counts[j] - counts[i] - k
		ans = min(ans, temp)
	print(ans)
	t -= 1


import bisect
for _ in range(int(input())):
	(w, k) = map(str, input().split())
	k = int(k)
	n = len(w)
	w = list(w)
	w.sort()
	w.append('0')
	c = 1
	l = 0
	l1 = []
	l2 = []
	for i in range(1, n + 1):
		if w[i] == w[i - 1]:
			c += 1
		else:
			a = bisect.bisect_left(l1, c)
			if a == l:
				l1.append(c)
				l2.append(1)
				l += 1
			elif l1[a] == c:
				l2[a] = l2[a] + 1
			else:
				l1.insert(a, c)
				l2.insert(a, 1)
				l += 1
			c = 1
	a = l1[-1] - l1[0]
	if a <= k:
		print(0)
	else:
		ans = n
		for i in range(l):
			temp = l2[i] * l1[i]
			for j in range(i + 1, l):
				p = l1[j] - l1[i]
				if p <= k:
					temp += l2[j] * l1[j]
				else:
					p1 = p - k
					temp += l2[j] * (l1[j] - p1)
			ans = min(ans, n - temp)
		print(ans)