#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } else return 0; }
using namespace std;

template<class A, class B> string to_string(pair<A, B> p);
template<class A> string to_string(A v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}

template<class A, class B> string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

using hashv = unsigned long long;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int cas; cin >> cas; while (cas--) {
		int k; cin >> k;
		string s; cin >> s;
		auto solve = [&](auto &dfs, int k, int ch, const string &s) -> string {
			if (k == 0) return s;
			int n = sz(s);
			if (n == 0) return s;
			if (s[0] == ch) {
				int r = 1;
				while (r < n && s[r] == ch) r++;
				return string(r, ch) + dfs(dfs, k, ch, string(s.begin() + r, s.end()));
			}
			vector<pii> segs;
			int l = 0;
			while (l < n) {
				if (s[l] != ch) l++;
				else {
					int r = l + 1;
					while (r < n && s[r] == ch) r++;
					segs.emplace_back(l, r - 1);
					l = r;
				}
			}
			// debug(ch, k, segs);
			if (sz(segs) == 0) return dfs(dfs, k, ch - 1, s);
			else if (sz(segs) <= k) {
				int cnt = 0, last = 0;
				for (auto [l, r]: segs) {
					cnt += r - l + 1;
					last = r + 1;
				}
				return string(cnt, ch) + dfs(dfs, k - sz(segs), ch - 1, string(s.begin() + last, s.end()));
			} else {
				vector<pii> vec;
				for (auto [l, r]: segs) {
					vec.emplace_back(r - l + 1, r + 1);
				}
				sort(all(vec), [](pii a, pii b) {
					if (a.first != b.first) return a.first > b.first;
					else return a.second < b.second;
				});
				int len = vec[k - 1].first;
				int mx = 0, sum = 0;
				rep (i, 0, k - 1) {
					chmax(mx, vec[i].second);
					sum += vec[i].first;
				}
				vi cand{mx};
				// debug(cand);
				rep(i, k, sz(vec) - 1) if (vec[i].first == len && chmax(mx, vec[i].second)) cand.push_back(mx);

				hashv base = 131;
				vector<hashv> pw(n + 1);
				pw[0] = 1;
				rep(i, 1, n) pw[i] = pw[i - 1] * base;
				vector<hashv> hx(n + 1);
				rep(i, 0, n - 1) {
					hx[i + 1] = hx[i] * base + s[i];
				}
				auto gethx = [&](int l, int r) { return hx[r + 1] - hx[l] * pw[r - l + 1]; };
				auto lcp = [&](int i, int j) {
					if (i > j) swap(i, j);
					int lo = 0, hi = n - j + 1;
					while (lo < hi) {
						int mid = (lo + hi) >> 1;
						if (gethx(i, i + mid - 1) != gethx(j, j + mid - 1)) hi = mid;
						else lo = mid + 1;
					}
					return hi - 1;
				};
				auto cmp = [&](int i, int j) {
					int l = lcp(i, j);
					return s[i + l] < s[j + l];
				};
				auto res = *max_element(all(cand), cmp);
				return string(sum, ch) + string(s.begin() + res, s.end());
			}
		};
		auto ans = solve(solve, k, 'z', s);
		puts(ans.c_str());
	}
	return 0;
}