#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
string s;
int k;
cin>>s>>k;
int ans=0;
for(int i=0;i<s.size();i++) {
unordered_map<char,int> map;
int dis=0;
for(int j=i;j<s.size();j++) {
if(map.count(s[j])==0) {
map[s[j]]++;
dis++;
}
else
map[s[j]]++;
if(dis<k)
continue;
unordered_map<char,int>:: iterator it=map.begin();
unordered_map<int,bool> map2;
while(it!=map.end()) {
if(map2.count(it->second)>0) {
ans++;
break;
}
map2[it->second]=true;
it++;
}
}
}
cout<<ans<<endl;
}
}