// 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;

#define MAX_N 100010
int RA[MAX_N], tempRA[MAX_N];
int SA[MAX_N], tempSA[MAX_N];
int c[MAX_N];

// uses Radix Sort as a subroutine to sort in O(n)
void CountingSort(int n, int k) {
    int i, sum, maxi = max(300, n);
    memset(c, 0, sizeof c);
    for (i = 0; i < n; i++)
        c[i+k < n ? RA[i+k] : 0]++;
    for (i = sum = 0; i < maxi; i++) {
        int t = c[i]; c[i] = sum; sum += t;
    }
    for (i = 0; i < n; i++)
        tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
    for (i = 0; i < n; i++)
        SA[i] = tempSA[i];
}

// Construct SA in O(n log n) time. Solves UVa Online Judge "Glass Beads" in .5 seconds
void ConstructSA(string T) {
    int i, k, r, n = T.size();
    for (i = 0; i < n; i++) RA[i] = T[i];
    for (i = 0; i < n; i++) SA[i] = i;
    for (k = 1; k < n; k <<= 1) {
        CountingSort(n, k);
        CountingSort(n, 0);
        tempRA[SA[0]] = r = 0;
        for (i = 1; i < n; i++)
            tempRA[SA[i]] =
                (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
        for (i = 0; i < n; i++)
            RA[i] = tempRA[i];
        if (RA[SA[n-1]] == n-1) break;
    }
}

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("?");

        ConstructSA(s);

        vi inverseSA(n+1);
        for (ll i = 0; i <= n; ++i) {
            inverseSA[SA[i]] = i;
        }

        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;
        }

        // 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;
    }
}