#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
int findMaxOccurrence(string S, int K) {
int n = S.length();
int maxOccurrence = 0;
unordered_map<string, int> charCount;
// Try all possible modifications to the string
for (int i = 0; i < n - 1; i++) {
if (S[i] == '?' || S[i] == 'A') {
if (S[i + 1] == '?' || S[i + 1] == 'B') {
string modifiedS = S;
modifiedS[i] = 'A';
modifiedS[i + 1] = 'B';
charCount["AB"] += 1;
maxOccurrence = max(maxOccurrence, charCount["AB"]);
if (K > 0) {
modifiedS[i] = 'B';
modifiedS[i + 1] = 'A';
charCount["AB"] += 1;
maxOccurrence = max(maxOccurrence, charCount["AB"]);
K--;
}
}
}
}
return maxOccurrence;
}
int main() {
int T; // Number of test cases
cin >> T;
for (int i = 0; i < T; i++) {
int N, K; // Length of string and maximum operations
cin >> N >> K;
string S; // Input string
cin >> S;
cout << findMaxOccurrence(S, K) << endl;
}
return 0;
}