#include<bits/stdc++.h>
namespace fastio {
using std::string;
const int bufl = 1 << 16;
const double base1[16] = {1,    1e-1, 1e-2,  1e-3,  1e-4,  1e-5,  1e-6,  1e-7,
                          1e-8, 1e-9, 1e-10, 1e-11, 1e-12, 1e-13, 1e-14, 1e-15};
const double base2[16] = {1,   1e1, 1e2,  1e3,  1e4,  1e5,  1e6,  1e7,
                          1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15};
struct IN {
    FILE* IT;
    char ibuf[bufl], *is = ibuf, *it = ibuf;
    IN() { IT = stdin; }
    IN(char* a) { IT = fopen(a, "r"); }
    inline char getChar() {
        if (is == it) {
            it = (is = ibuf) + fread(ibuf, 1, bufl, IT);
            if (is == it)
                return EOF;
        }
        return *is++;
    }
    template <typename Temp>
    inline void getInt(Temp& a) {
        a = 0;
        int b = 0, c = getChar();
        while (c < 48 || c > 57)
            b ^= (c == 45), c = getChar();
        while (c >= 48 && c <= 57)
            a = (a << 1) + (a << 3) + c - 48, c = getChar();
        if (b)
            a = -a;
    }
    template <typename Temp>
    inline void getDouble(Temp& a) {
        a = 0;
        int b = 0, c = getChar(), d = 0;
        __int128 e = 0, f = 0;
        while (c < 48 || c > 57)
            b ^= (c == 45), c = getChar();
        while (c >= 48 && c <= 57)
            e = (e << 1) + (e << 3) + c - 48, c = getChar();
        if (c == 46) {
            c = getChar();
            while (c >= 48 && c <= 57)
                d++, f = (f << 1) + (f << 3) + c - 48, c = getChar();
        }
        a = e + base1[d] * f;
        if (b)
            a = -a;
    }
    IN& operator>>(char& a) {
        a = getChar();
        return *this;
    }
    IN& operator>>(char* a) {
        do {
            *a = getChar();
        } while (*a <= 32);
        while (*a > 32)
            *++a = getChar();
        *a = 0;
        return *this;
    }
    IN& operator>>(string& a) {
        char b = getChar();
        while (b <= 32)
            b = getChar();
        while (b > 32)
            a += b, b = getChar();
        return *this;
    }
    IN& operator>>(int& a) {
        getInt(a);
        return *this;
    }
    IN& operator>>(long long& a) {
        getInt(a);
        return *this;
    }
    IN& operator>>(__int128& a) {
        getInt(a);
        return *this;
    }
    IN& operator>>(float& a) {
        getDouble(a);
        return *this;
    }
    IN& operator>>(double& a) {
        getDouble(a);
        return *this;
    }
    IN& operator>>(long double& a) {
        getDouble(a);
        return *this;
    }
};
struct OUT {
    FILE* IT;
    char obuf[bufl], *os = obuf, *ot = obuf + bufl;
    int Eps;
    long double Acc;
    OUT() { IT = stdout, Eps = 6, Acc = 1e-6; }
    OUT(char* a) { IT = fopen(a, "w"), Eps = 6, Acc = 1e-6; }
    inline void ChangEps(int x = 6) { Eps = x; }
    inline void flush() {
        fwrite(obuf, 1, os - obuf, IT);
        os = obuf;
    }
    inline void putChar(int a) {
        *os++ = a;
        if (os == ot)
            flush();
    }
    template <typename Temp>
    inline void putInt(Temp a) {
        if (a < 0) {
            putChar(45);
            a = -a;
        }
        if (a < 10) {
            putChar(a + 48);
            return;
        }
        putInt(a / 10);
        putChar(a % 10 + 48);
    }
    template <typename Temp>
    inline void putDouble(Temp a) {
        if (a < 0) {
            putChar(45);
            a = -a;
        }
        __int128 b = a;
        putInt(b);
        a -= b;
        a *= base2[Eps];
        b = a + Acc;
        putChar(46);
        putInt(b);
    }
    OUT& operator<<(char a) {
        putChar(a);
        return *this;
    }
    OUT& operator<<(char* a) {
        while (*a > 32)
            putChar(*a++);
        return *this;
    }
    OUT& operator<<(string a) {
        for (auto c : a)
            putChar(c);
        return *this;
    }
    OUT& operator<<(int a) {
        putInt(a);
        return *this;
    }
    OUT& operator<<(long long a) {
        putInt(a);
        return *this;
    }
    OUT& operator<<(__int128 a) {
        putInt(a);
        return *this;
    }
    OUT& operator<<(float a) {
        putDouble(a);
        return *this;
    }
    OUT& operator<<(double a) {
        putDouble(a);
        return *this;
    }
    OUT& operator<<(long double a) {
        putDouble(a);
        return *this;
    }
    ~OUT() { flush(); }
};
}  // namespace fastio
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;


void solve(){
    int n,k;fin>>n>>k;
    std::string st;fin>>st;
    if(n < 7){
        fout<<0<<'\n';
        return;
    }
    st = st + st;
    int cnt = 0;
    int ans = 0;
    std::vector<int> mark(2 * n + 2);
    for(int i = 0;i + 6 < n;i++){
        if(st.substr(i, 7) == "nanjing")cnt++, mark[i] ++;
    }
    ans = cnt;

    for(int i = 0;i < std::min(n, k);i++){
        if(mark[i])cnt--;
        if(st.substr(i + n - 6, 7) == "nanjing")cnt++;
        ans = std::max(ans, cnt);
    }

    fout<<ans<<'\n';
}

signed main(){
    int t = 1;
    fin>>t;
    while(t--)solve();

}