use std::io;

fn main(){
    let core = "edgnb";
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    let mut n: i32 = s.trim().parse().unwrap();
    
    for i in 0..n{
        let mut js = 0;
        let mut cnt = 0;
        let mut str = String::new();
        io::stdin().read_line(&mut str).unwrap();
        let mut num = String::new();
        io::stdin().read_line(&mut num).unwrap();
        let mut m: i32 = num.trim().parse().unwrap();

        let mut j = 0;
        while j <= str.len() - 5{
            if &str[j..j+5] == core {
                js += 1;
                j += 5;
                if js >= m {
                    cnt += 1;
                }
            } else{
                js = 0;
                j += 1;
            }
        }

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