// Same solution as the others... Far worse code ;)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <unordered_set>
#include <queue>
#include <functional>

#define f first
#define s second

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<char, ll> ci;
typedef vector<ci> vci;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

bool myfunction (ci left, ci right) {
    if (left.f < right.f) return true;
    else if (left.f == right.f) return left.s > right.s;
    else return false;
}

int main() {
	ll c;
    cin >> c;
    for (ll cs = 1; cs <= c; ++cs) {
        ll k;
        string s;
        cin >> k >> s;

        ll n = s.size();
        s = s + string("?");

        vci s_rev(n);
        for (ll i = 0; i < n; ++i) {
            s_rev[i] = ci(s[i], i);
        }
        sort(s_rev.rbegin(), s_rev.rend(), myfunction);
        
        // handle all before the last letter    
        stringstream output;
        char cur_letter = s_rev[0].f;
        ll cost = 0;
        ll furthest_right = -1; // should be the last character of the last substring guaranteed to be included
        ll num = 0;
        for (ll i = 0; true; ++i) {
            if (i == s_rev.size() || s_rev[i].f != cur_letter) {
                if (cost <= k) {
                    for (ll j = 0; j < num; ++j) {
                        output << cur_letter;
                    }
                    
                    k -= cost;
                    cost = 0;
                    num = 0;
                    furthest_right = max(furthest_right, s_rev[i-1].s);
                    if (k == 0) break;
                    if (i < s_rev.size()) {
                        cur_letter = s_rev[i].f;
                    } else break;
                } else break;
            }
            
            if (s_rev[i].s < furthest_right) continue;
            if (i == 0 && s_rev[i].s != 0 || i > 0 && s_rev[i].s != s_rev[i-1].s+1 && s_rev[i].s != furthest_right+1) {
                ++cost;
            }
            ++num;
        }

        if (cost <= k) {
            for (ll i = furthest_right+1; i < n; ++i) {
                output << s[i];
            }
            cout << output.str() << endl;
            continue;
        }

        while (furthest_right+1 < n && s[furthest_right+1] == cur_letter) {  // extend previous for free
            ++furthest_right;
            output << cur_letter;
          //  cerr << "inc output" << endl;
        }

        // find size of stream of letters of final letter
        priority_queue<ii> best_size;
        for (ll i = furthest_right+1; i < n; ) {
            if (s[i] == cur_letter) {
                ll cur_size = 0;
                for (ll j = i; j < n; ++j) {
                    if (s[j] == cur_letter) ++cur_size;
                    else break;
                }
                best_size.push(ii(cur_size, i+cur_size));
                i += cur_size;
            }
            else ++i;
        }

        best_size.push(ii(-1, -1));  // add dummy so if condition is hit if all of same size or similar

        // determine the size of this stream, adding larger streams to result
        ii last_size = best_size.top();
        ll final_size;
        priority_queue<ii, vii, greater<ii>> all_of_size;
        while (true) {
            ii top = best_size.top(); 
            best_size.pop();
            if (top.f != last_size.f) {
                if (all_of_size.size() > k) {
                    final_size = all_of_size.top().f;
                    break;
                }
                for (ll i = 0; i < all_of_size.size(); ++i) {
                    for (ll j = 0; j < last_size.f; ++j) {
                        output << cur_letter;
                    }
                }
                k -= all_of_size.size();
                furthest_right = max(furthest_right, last_size.s);
                if (k == 0) {
                    for (ll i = furthest_right; i < n; ++i) {
                        output << s[i];
                    }
                    cout << output.str() << endl;
                    break;
                }
                all_of_size = priority_queue<ii, vii, greater<ii>>();
                last_size = top;
            }
            all_of_size.push(top);
        }

        if (k == 0) continue;

        // add the first k-1 WLOG
        while (k > 1) {
            all_of_size.pop();
            for (ll j = 0; j < final_size; ++j) {
                output << cur_letter;
            }
            --k;
        }

        // hack to not use suffix array
        vi inverseSA(n+1, 0);
        unordered_set<ll> check;
        priority_queue<ii, vii, greater<ii>> temp = all_of_size;
        while (!temp.empty()) {
            ii top = temp.top();
            temp.pop();
            ll pos = max(top.s, furthest_right);
            check.insert(pos);
        }
        vector<pair<string, ll>> suffixes;
        for (auto it : check) {
            suffixes.push_back(make_pair(s.substr(it), it));
        }
        sort(suffixes.begin(), suffixes.end());
        for (ll i = 0; i < suffixes.size(); ++i) {
            inverseSA[suffixes[i].s] = i;
        }

        // determine which of the remaining will maximize the resulting alphabetical order of string
        priority_queue<ii> final_choices;
        while (!all_of_size.empty()) {
            ii top = all_of_size.top();
            all_of_size.pop();
            ll pos = max(top.s, furthest_right);
            final_choices.push(ii(inverseSA[pos], pos)); // use inverseSA to get sorting of particular ending point
        }

        // add characters of cur_letter of final choice
        for (ll j = 0; j < final_size; ++j) {
            output << cur_letter;
        }

        // add remaining string of s to final choice
        ii final_choice = final_choices.top();  // this is our final choice
        for (ll i = final_choice.s; i < n; ++i) {
            output << s[i];
        }

        cout << output.str() << endl;
    }
}