#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(x) for(ll i = 1; i <= x; i ++)

void solve(){
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = s + s;
    ll ans1 = 0;
    if(n < 7) { cout << 0 << endl;return ; }
    vector<ll> a(n + 1);
    for(int i = 0; i < n - 7 + 1 ; i ++){
        if(s.substr(i, 7) == "nanjing"){
            ans1 ++;
            i += 6;
        }
    }
    for(int i = n - 6; i < 2 * n - 6; i ++){
        if(s.substr(i, 7) == "nanjing"){
            a[i - (n - 5)] ++;
            i += 6;
        }
    }
    f(n){
        a[i] += a[i - 1];
    }

    cout << ans1 + k / n * a[n] + a[k % n] << endl;
}

int main (){
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}