#include<bits/stdc++.h>
#define int long long
using namespace std;

int t;

const string narek = "narek";

void solve(){
    int ans = 0;
    int n , m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 0;i < n;i ++){
        cin >> s[i];
    }
    vector<int> dp(5 , -1e9) , ndp;
    dp[0] = 0;
    for(int i = 0; i < n;i ++){
        ndp = dp;
        for(int k = 0;k < 5;k ++){
            if(dp[k] == -1e9) continue;
            int nxt = k , score = 0;
            for(int j = 0;j < m;j ++){
                int idx = narek.find(s[i][j]);
                if(idx == -1) continue;
                if(nxt == idx){
                    nxt = (nxt + 1) % 5;
                    score++;
                }
                else score--;
            }
            ndp[nxt] = max(ndp[nxt] , dp[k] + score);
        }
        dp = ndp;
    }
    for(int i = 0;i < 5;i ++) ans = max(ans , dp[i] - 2 * i);
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}