#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;
}
}