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: interview

Starter code:

Solutions:
# cook your dish here
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)


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()
 #counts = counts[::-1]
 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 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)


# cook your dish here

t = int(input())
while t:
 w,k = input().split()
 k = int(k)
 char = {}
 for c in w:
  if c not in char.keys():
   char[c] = 1
  else:
   char[c] += 1
 counts = list(char.values())
 counts.sort()
 #counts = counts[::-1]
 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

##//author : 'Amit Singh Sansoya @amit3200'
##//it was all meant to happen as i was all talk!
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)