use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock().lines();

    let t: usize = input.next().unwrap().unwrap().trim().parse().unwrap();  // Read number of test cases
    for _ in 0..t {
        let mut first_line = input.next().unwrap().unwrap();
        let mut first_line_split = first_line.split_whitespace();
        
        let n: usize = first_line_split.next().unwrap().parse().unwrap();  // Read n
        let k: usize = first_line_split.next().unwrap().parse().unwrap();  // Read k

        let s: String = input.next().unwrap().unwrap();  // Read the string s
        let mut p = s.clone();  // Copy the string s to p
        let mut ans: i64 = 0;
        let mut temp = k;
        let mut cnt_a: i64 = s.chars().filter(|&c| c == 'A').count() as i64;

        // Track occurrences of 'A' counts
        let mut occ_a = Vec::new();

        // Handle the '?' characters from the back and decrement temp accordingly
        for i in (0..n).rev() {
            if temp == 0 {
                break;
            }
            if s.chars().nth(i).unwrap() == 'A' {
                cnt_a -= 1;
            }
            if s.chars().nth(i).unwrap() == '?' {
                p.replace_range(i..i+1, "B");
                temp -= 1;
                occ_a.push(cnt_a);
            }
        }

        // Count 'B's in modified string p
        let mut cnt_b: i64 = p.chars().filter(|&c| c == 'B').count() as i64;
        let mut temp_b = cnt_b;

        // Calculate the initial answer
        for (i, ch) in p.chars().enumerate() {
            if ch == 'B' {
                temp_b -= 1;
            }
            if s.chars().nth(i).unwrap() == 'A' {
                ans += temp_b;
            }
        }

        let mut answer = ans;
        let mut pos: i64 = occ_a.len() as i64 - 1;
        let mut new_a = 0;

        // Update the answer by adjusting for '?' characters
        for (i, ch) in s.chars().enumerate() {
            if cnt_b == 0 || pos < 0 {
                break;
            }
            if ch == 'B' {
                cnt_b -= 1;
            }
            if ch == '?' {
                ans -= occ_a[pos as usize];
                cnt_b -= 1;
                pos -= 1;
                ans += cnt_b;
                ans -= new_a;
                new_a += 1;
            }
            answer = answer.max(ans);
        }

        println!("{}", answer);
    }
}