#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <deque>
#include <algorithm>
#include <math.h>
#include <random>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
#define double long double
#define Matrix vector<vector<int> >
#define kektor vector
#define pp pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

int RandInt(int min, int max) {
    if (max < min) {
        swap(min, max);
    }
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<int> dist(min, max);
    return dist(mt);
}

const int maxn = 2e5 + 1, mod = 1e9, N = 100, K = 32;
bool debug = false;
int dp[N][K][K][K][K], n, k1;
string s;

void inic() {
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j <= k1; ++j) {
			for (int i1 = 0; i1 <= k1; ++i1) {
				for (int j1 = 0; j1 <= k1; ++j1) {
					for (int k = 0; k <= k1; ++k) {
						dp[i][j][i1][j1][k] = 1e9;
					}
				}
			}
		}
	}
	dp[0][0][0][0][0] = (s[0] != 'c');
	if (s[0] == 'c') {
		dp[0][1][0][0][0] = 0;
	}
	for (int i = 1; i < s.size(); ++i) {
		for (int j = 0; j <= k1; ++j) {
			for (int i1 = 0; i1 <= k1; ++i1) {
				for (int j1 = 0; j1 <= k1; ++j1) {
					for (int k = 0; k <= k1; ++k) {
						dp[i][j][i1][j1][k] = min(dp[i][j][i1][j1][k], dp[i - 1][j][i1][j1][k] + 1);
						if (s[i] == 'c') {
							if (j - 1 >= 0)
								dp[i][j][i1][j1][k] = min(dp[i][j][i1][j1][k], dp[i - 1][j - 1][i1][j1][k]);
						}
						if (s[i] == 'h') {
							if (i1 - j >= 0)
								dp[i][j][i1][j1][k] = min(dp[i][j][i1][j1][k], dp[i - 1][j][i1 - j][j1][k]);
						}
						if (s[i] == 'e') {
							if (j1 - i1 >= 0)
								dp[i][j][i1][j1][k] = min(dp[i][j][i1][j1][k], dp[i - 1][j][i1][j1 - i1][k]);
						}
						if (s[i] == 'f') {
							if (k - j1 >= 0)
								dp[i][j][i1][j1][k] = min(dp[i][j][i1][j1][k], dp[i - 1][j][i1][j1][k - j1]);
						}
					}
				}
			}
		}
	}
	int ans = 1e9;
	for (int j = 0; j <= k1; ++j) {
		for (int i1 = 0; i1 <= k1; ++i1) {
			for (int j1 = 0; j1 <= k1; ++j1) {
				for (int k = 0; k <= k1; ++k) {
					ans = min(ans, dp[s.size() - 1][j][i1][j1][k]);
				}
			}
		}
	}
	if (ans == 1e9) {
		cout << -1 << '\n';
		return;
	}
	cout << ans << '\n';
	return;
}

void solve() {
	int test;
	cin >> test;
	for (int dd = 0; dd < test; ++dd) {
		cin >> n >> k1 >> s;
		inic();

	}
}

signed main() {
    /*!

    !*/
    cout.precision(10);
    cout << fixed;
    if (!debug) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    }
    freopen("TASK.in", "r", stdin);
    freopen("TASK.out", "w", stdout);
    solve();
    return 0;
}