#include <bits/stdc++.h>

using namespace std;


int MAX_ALPHABET;
int MAXN;

int subtask;

string t;
int maxHammingDistance;
int alphabetSize;

void readInput() {
  switch (subtask) {
    case 1: MAX_ALPHABET = 1; MAXN = 50; break; 
    case 2: MAX_ALPHABET = 3; MAXN = 12; break; 
    case 3: MAX_ALPHABET = 2; MAXN = 50; break; 
    case 4: MAX_ALPHABET = 3; MAXN = 50; break; 
  } 
  cin >> alphabetSize >> maxHammingDistance;
  cin >> t;
  /*
	char mx = 'a';
  for (int i = 0; i < t.size(); i++) {
    assert(t[i] >= 'a' && t[i] <= 'z');
    mx = max(mx, t[i]);
  }
  assert(alphabetSize <= MAX_ALPHABET);
  assert(mx - 'a' + 1 <= alphabetSize);
  assert(t.size() >= 1 && t .size() <= MAXN);
	*/
}

int calcHammingDistance(string s, string t) {
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != t[i]) {
      ans++;
    }
  }
  return ans;
}

int solveSubtask1() {
  if (t.size() >= 3) {
    return 0;
  }
  vector<string> cands;
  string s = "";
	for (int i = 0; i < t.size(); i++) {
		s += "a";
	}
	return calcHammingDistance(s, t) <= maxHammingDistance;
}

void rec(string s, int alphabetSize, vector<string> &data, bool fast, int maxn) {
  if (s.size() > maxn) {
		return;
	}
	data.push_back(s);
  for (char ch = 'a'; ch < 'a' + alphabetSize; ch++) {
    int ok = true;
    for (int i = 0; i < s.size() && ok; i++) {
			if (fast) {
				int k = s.size();
				if ((i + k) % 2 == 0) {
					int j = (i + k) / 2;
					if (s[i] == s[j] && s[j] == ch) {
						ok = false;
						break;
					}
				} 
			} else {
				for (int j = i + 1; j < s.size(); j++) {
					int k = s.size();
					if (j - i == k - j && s[i] == s[j] && s[j] == ch) {
						ok = false;
						break;
					}
				}	
			}
    } 
    if (ok) {
      string t = s;
      t += ch;
      rec(t, alphabetSize, data, fast, maxn);
    }
  } 
}

vector<string> genGoodStringsFast(int alphabetSize, int maxn) {
  vector<string> data;
	rec("", alphabetSize, data, true, maxn);
  return data;
}

vector<string> genGoodStringsSlow(int alphabetSize, int maxn) {
  vector<string> data;
	rec("", alphabetSize, data, false, maxn);
  return data;
}

vector<string> oneAlphabetGoodStrings, twoAlphabetGoodStrings, threeAlphabetGoodStrings;

int solveSubtask2() {
  if (alphabetSize == 1) {
    return solveSubtask1(); 
  } else {
		vector<string> data = genGoodStringsFast(alphabetSize, (int) t.size());
    int ans = 0;
    for (string s: data) {
      if (s.size() == t.size()) {
        if (calcHammingDistance(s, t) <= maxHammingDistance) {
          ans++;
        }
      }
    }
		return ans;
  } 
}

int solveSubtask3() {
	int ans = 0;
	for (string s: twoAlphabetGoodStrings) {
		if (s.size() > t.size()) {
			break;
		}
		if (s.size() == t.size()) {
			if (calcHammingDistance(s, t) <= maxHammingDistance) {
				ans++;
			}
		}
	}
	return ans;
}

int solveSubtask4() {
	int ans = 0;
	for (string s: threeAlphabetGoodStrings) {
		if (s.size() > t.size()) {
			break;
		}
		if (s.size() == t.size()) {
			if (calcHammingDistance(s, t) <= maxHammingDistance) {
				ans++;
			}
		}
	}
	return ans;
}

int solve() {
  switch (subtask) {
    case 1: return solveSubtask1();
    case 2: return solveSubtask2();
    case 3: return solveSubtask3();
    case 4: return solveSubtask4();
  }
}

void preprocess() {
	oneAlphabetGoodStrings = genGoodStringsFast(1, 50);
	twoAlphabetGoodStrings = genGoodStringsFast(2, 50);		
	threeAlphabetGoodStrings = genGoodStringsFast(3, 50);		
}

int cntIt(vector<string> data) {
	int ans = 0;
	for (string s : data) {
		if (s.size() == t.size() && calcHammingDistance(s, t) <= maxHammingDistance) {
			ans++;
		}
	}
	return ans;
}

int solveEverything() {
	switch (alphabetSize) {
		case 1 : return cntIt(oneAlphabetGoodStrings);
		case 2 : return cntIt(twoAlphabetGoodStrings);
		case 3 : return cntIt(threeAlphabetGoodStrings);
	}
}

int main() {
  	preprocess();
	/*
	cout << "done " << endl;
	{
		int mx = 0;
		for (string s : twoAlphabetGoodStrings) {
			mx = max(mx, (int) s.size());
		}
		cout << "mx " << mx << " total " << twoAlphabetGoodStrings.size() << endl;
	}
	{
		int mx = 0;
		for (string s : threeAlphabetGoodStrings) {
			mx = max(mx, (int) s.size());
		}
		cout << "mx " << mx << " total " << threeAlphabetGoodStrings.size() << endl;
	}
	return 0;
	*/

	int T;
  	cin >> T;
  	assert(T >= 1 && T <= 50);
  	while (T--) {
	    //subtask = 1;
			readInput();
	    //int ans = solve();
	    int ans = solveEverything();
		cout << ans << endl;
  	}

  	return 0;
}