#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"] = max(charCount["AB"], charCount["AB"] + 1);
                maxOccurrence = max(maxOccurrence, charCount["AB"]);

                if (K > 0) {
                    modifiedS[i] = 'B';
                    modifiedS[i + 1] = 'A';
                    charCount["AB"] = max(charCount["AB"], 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;
}