#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
char s[100001];
long int k, a[26]={0}, i, start, end, count_end=1, count_start=1, ans=0;
cin>>s>>k;
sort(s,s+strlen(s));
for(i=0;i<strlen(s);i++)
a[s[i]-97]++;
sort(a,a+26);
i=0;
while(a[i]==0 && i<=25)
i++;
start=i;
end=25;
while(a[end]-a[start]>k && start<end)
{
while(a[start]==a[start+1])
{
start++;
count_start++;
}
while(a[end]==a[end-1])
{
end--;
count_end++;
}
if(a[start]*count_start>(a[end]-a[start]-k)*count_end)
{
ans+=(a[end]-a[start]-k)*count_end;
end--;
}
else
{
ans+=a[start]*count_start;
start++;
}
count_start=1;
count_end=1;
}
cout<<ans<<endl;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1haW4oKQp7CiAgICBpbnQgdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCSAgICBjaGFyIHNbMTAwMDAxXTsKCQlsb25nIGludCBrLCBhWzI2XT17MH0sIGksIHN0YXJ0LCBlbmQsIGNvdW50X2VuZD0xLCBjb3VudF9zdGFydD0xLCBhbnM9MDsKCQljaW4+PnM+Pms7CgkJc29ydChzLHMrc3RybGVuKHMpKTsKCQlmb3IoaT0wO2k8c3RybGVuKHMpO2krKykKCQlhW3NbaV0tOTddKys7CgkJc29ydChhLGErMjYpOwoJCWk9MDsKCQl3aGlsZShhW2ldPT0wICYmIGk8PTI1KQoJCWkrKzsKCQlzdGFydD1pOwoJCWVuZD0yNTsKCQl3aGlsZShhW2VuZF0tYVtzdGFydF0+ayAmJiBzdGFydDxlbmQpCgkgICAgewoJICAgIAl3aGlsZShhW3N0YXJ0XT09YVtzdGFydCsxXSkKCSAgICAJewoJCQlzdGFydCsrOwoJICAgICAgICBjb3VudF9zdGFydCsrOwoJCQl9IAoJCQl3aGlsZShhW2VuZF09PWFbZW5kLTFdKQoJICAgIAl7CgkJCWVuZC0tOwoJICAgIAljb3VudF9lbmQrKzsKCSAgICAgICAgfQoJICAgICAgICBpZihhW3N0YXJ0XSpjb3VudF9zdGFydD4oYVtlbmRdLWFbc3RhcnRdLWspKmNvdW50X2VuZCkKCSAgICAgICAgewoJICAgICAgICBhbnMrPShhW2VuZF0tYVtzdGFydF0taykqY291bnRfZW5kOwoJICAgICAgICBlbmQtLTsKCSAgICB9CgkJCWVsc2UKCSAgICAgICAgewoJCQlhbnMrPWFbc3RhcnRdKmNvdW50X3N0YXJ0OwoJICAgICAgICBzdGFydCsrOwoJICAgIH0KCSAgICAgICAgY291bnRfc3RhcnQ9MTsKCSAgICAgICAgY291bnRfZW5kPTE7CgkgICAgfQoJCQoJCWNvdXQ8PGFuczw8ZW5kbDsKCX0KCXJldHVybiAwOwp9