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| ≤ 10^5
0 ≤ K ≤ 10^5
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.
#top down dp
# def function(b,i,j,matrix):
# 	if i>=j:
# 		return 0
# 	if b[j]-b[i]<=k:
# 		return 0
# 	if matrix[i][j]!=-1:
# 		return matrix[i][j]
# 	#matrix[i][j]=min(b[i]+matrix[i+1][j],matrix[i][j-1]+b[j]-b[i]-k)
# 	m1=b[i]+function(b,i+1,j,matrix)
# 	m2=b[j]-b[i]-k+function(b,i,j-1,matrix)
# 	matrix[i][j]=min(m1,m2)
# 	return matrix[i][j]

#bottom up dp
def function(b,n):
	matrix=[[0 for x in xrange(n)]for x in xrange(n)]
	for i in xrange(n-1,-1,-1):
		for j in xrange(0,n):
			if i>=j:
				matrix[i][j]=0
			elif b[j]-b[i]<=k:
				matrix[i][j]=0
			else:
				matrix[i][j]=min(b[i]+matrix[i+1][j],matrix[i][j-1]+b[j]-b[i]-k)
	return matrix[0][n-1]				

def get_k_good(word,k):
	a={}
	for i in word:
		if i in a:
			a[i]+=1
		else:
			a[i]=1
	b=sorted([a[i]for i in a])
	n=len(b)
	#matrix=[[-1 for i in xrange(n)] for i in xrange(n)]
	#return function(b,0,n-1,matrix)
	return function(b,n)

t=input()
while(t>0):
	word,k=raw_input().strip().split()
	k=int(k)
	print get_k_good(word,k)
	t-=1