#include <bits/stdc++.h>
using namespace std;

using cat = long long;

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for(int t = 0; t < T; t++) {
		string S;
		int K;
		cin >> S >> K;
		int N = S.length(), ans = 0;
		// try all substrings
		for(int i = 0; i < N; i++) {
			int occ[26] = {};
			int mxocc = 0, cnt = 0;
			for(int j = i; j >= 0; j--) {
				if(occ[S[j]-'a'] == 0) cnt++;
				mxocc = max(mxocc, ++occ[S[j]-'a']);
				if(cnt >= K && mxocc*cnt == i-j+1) ans++;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}