def main():
    t = int(input())  # Number of test cases
    for _ in range(t):
        n, k = map(int, input().split())  # Read n and k
        s = input()  # Read string s
        ans = 0
        temp = k
        p = list(s)  # Copy the string to p as a list of characters (for mutability)
        
        cntA = s.count('A')  # Count occurrences of 'A' in the string
        occA = []
        
        # Traverse the string from the back and replace '?' with 'B'
        for i in range(n-1, -1, -1):
            if temp == 0:
                break
            if s[i] == 'A':
                cntA -= 1
            if s[i] == '?':
                p[i] = 'B'
                temp -= 1
                occA.append(cntA)
        
        # Count 'B's in the modified string p
        cntB = p.count('B')
        tempB = cntB
        
        # Calculate the initial answer
        for i in range(n):
            if p[i] == 'B':
                tempB -= 1
            if s[i] == 'A':
                ans += tempB
        
        answer = ans
        pos = len(occA) - 1
        newA = 0

        # Update the answer based on occurrences of '?'
        for i in range(n):
            if pos < 0:
                break
            if s[i] == 'B':
                cntB -= 1
            if s[i] == '?':
                ans -= occA[pos]
                cntB -= 1
                pos -= 1
                ans += cntB
                ans -= newA
                newA += 1
            answer = max(answer, ans)
        
        print(answer)


if __name__ == "__main__":
    main()