#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
ll read(){
    ll X = 0 ,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
    return X*r;
}
const int N = 1e6+10;
int n,k;
string s;
void solve(){
    n = read(); k = read();
    cin >> s;
    s = s+s;
    int ans = 0;
    for(int i=0;i<n;i++){
        if(i+7 < 2*n && s.substr(i,7) == "nanjing"){
            if(i+7-n <= k) ans++;
        }
    }
    cout << ans << "\n";
}
int main(){
    int T = read();
    while(T--) solve();
	return 0;
}