#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void suffix_array(string S, vector<int> &sa)
{
	int n = S.size();
	sa.resize(n);
	vector<int> r(n), _r(n), p(n), id(n);
	for(int i = 0; i < n; ++i) sa[i] = i;
	sort(sa.begin(), sa.end(), [&](int i, int j) {
		return S[i] < S[j];
	});
	for(int i = 1; i < n; ++i)
		r[sa[i]] = r[sa[i - 1]] + (S[sa[i]] != S[sa[i - 1]]);
	for(int d = 1; d < n; d *= 2)
	{
		for(int i = 0; i < n; ++i) p[i] = 0;
		for(int i = 0; i < n; ++i) p[r[i]]++;
		for(int i = 1; i < n; ++i) p[i] += p[i - 1];
		int j = 0;
		for(int i = n - d; i < n; ++i) id[j++] = i;
		for(int i = 0; i < n; ++i)
			if(sa[i] >= d) id[j++] = sa[i] - d;
		for(int i = n - 1; i >= 0; --i)
			sa[--p[r[id[i]]]] = id[i];
		_r[sa[0]] = 0;
		for(int i = 1; i < n; ++i)
		{
			if(r[sa[i]] != r[sa[i - 1]])
				_r[sa[i]] = _r[sa[i - 1]] + 1;
			else {
				int x = (sa[i] + d < n) ? r[sa[i] + d] : -1;
				int y = (sa[i - 1] + d < n) ? r[sa[i - 1] + d] : -1;
				_r[sa[i]] = _r[sa[i - 1]] + (x != y);
			}
		}
		r = _r;
	}
}

string f(string &s, vector<int> &ord, int st, int k, bool pf)
{
	if(s.size() == st) return string();
	// cout << st << ' ' << k << ' ' << pf << endl;

	char mx = 0;
	for(int i = st; i < s.size(); ++i) mx = max(mx, s[i]);
	int cnt = 0;
	for(int i = st; i < s.size(); ++i) if(s[i] == mx) ++cnt;

	if(pf)
	{
		int pt = st;
		while(pt < s.size() && s[pt] == mx) ++pt;
		if(pt - st == cnt) return string(pt - st, mx) + f(s, ord, pt, k, true);
		else return string(pt - st, mx) + f(s, ord, pt, k, false);
	}

	vector<pii> V;
	int len = 0;
	for(int i = st; i <= s.size(); ++i)
	{
		if(i == s.size() || s[i] != mx)
		{
			if(len)
			{
				V.push_back({ i, len });
				len = 0;
			}
		}
		else ++len;
	}

	if(V.size() >= k)
	{
		priority_queue<int, vector<int>, greater<int>> Q;
		int sum = 0;
		for(int i = 0; i < k - 1; ++i) Q.push(V[i].ss), sum += V[i].ss;
		
		vector<pair<pii, int>> W;
		for(int i = k - 1; i < V.size(); ++i)
		{
			W.push_back({ { sum + V[i].ss, ord[V[i].ff] }, i });
			sum += V[i].ss;
			Q.push(V[i].ss);
			sum -= Q.top();
			Q.pop();
		}

		int t = (*max_element(W.begin(), W.end())).ss;
		int p = (*max_element(W.begin(), W.end())).ff.ff;
		// cout << t << ' ' << p << ' ' << V[t].ff << endl;
		return string(p, mx) + string(s.begin() + V[t].ff, s.end());
	}

	else
	{
		// cout << 0 << endl;
		string ret(cnt, mx);
		return ret + f(s, ord, V.back().ff, k - V.size(), true);
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	int T; cin >> T;
	while(T--)
	{
		int k; cin >> k;
		string s; cin >> s;
		vector<int> sa;
		suffix_array(s, sa);
		vector<int> ord(s.size());
		for(int i = 0; i < s.size(); ++i) ord[sa[i]] = i;
		ord.push_back(-1);
		cout << f(s, ord, 0, k, true) << '\n';
	}
}