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


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

