#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
const int N=1e5+50;

char str[N];
int sa[N],rk[N];
int n;
void build() {
    static int _sa[N],A[N],B[N],cnt[N];
    int m=260;
    FOR(i,0,m) cnt[i]=0;
    FOR(i,1,n) ++cnt[str[i]];
    FOR(i,1,m) cnt[i]+=cnt[i-1];
    DOR(i,n,1) sa[cnt[str[i]]--]=i;
    rk[sa[1]]=1;
    FOR(i,2,n) rk[sa[i]]=rk[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
    for(int l=1; l<n && (m=rk[sa[n]])<n; l<<=1) {
        FOR(i,1,n) A[i]=(i+l<=n)?rk[i+l]:0;
        FOR(i,1,n) B[i]=rk[i];
        int p=0;
        FOR(i,n-l+1,n) _sa[++p]=i;
        FOR(i,1,n) if(sa[i]>l) _sa[++p]=sa[i]-l;
        FOR(i,0,m) cnt[i]=0;
        FOR(i,1,n) ++cnt[B[_sa[i]]];
        FOR(i,1,m) cnt[i]+=cnt[i-1];
        DOR(i,n,1) sa[cnt[B[_sa[i]]]--]=_sa[i];
        rk[sa[1]]=1;
        FOR(i,2,n) rk[sa[i]]=rk[sa[i-1]]+(A[sa[i]]!=A[sa[i-1]] || B[sa[i]]!=B[sa[i-1]]);
    }
}
string ans;
void solve(char c,int s,int m) {
    // cerr << s << endl;
    while(s<=n && str[s]==c) ans.push_back(str[s++]);
    if(s>n) return ;
    if(m==0) {
        FOR(i,s,n) ans.push_back(str[i]);
        return ;
    }
    vector<pair<int,int>> vec;
    for(int i=s; i<=n; ++i) {
        if(str[i]!=c) continue;
        int j=i;
        while(j<n && str[j+1]==c) ++j;
        vec.push_back({i,j});
        i=j;
    }
    if(m>=vec.size()) {
        for(auto [l,r]: vec) {
            // cerr << l << ' ' << r << endl;
            FOR(i,l,r) ans.push_back(c);
        }
        if(c>='a') {
            solve(c-1,vec.size()?vec.back().second+1:s,m-vec.size());
        }
        return ;
    }
    priority_queue<int> Q;
    int tot=0;
    pair<int,int> mx;
    for(auto [l,r]: vec) {
        mx=max(mx,make_pair(tot+r-l+1,rk[r+1]));
        Q.push(-(r-l+1));
        tot+=r-l+1;
        if(Q.size()==m) {
            tot+=Q.top();
            Q.pop();
        }
    }
    if(mx.second==0) mx.second=n+1;
    else mx.second=sa[mx.second];
    // cerr << mx.first << endl;
    FOR(i,1,mx.first) ans.push_back(c);
    FOR(i,mx.second,n) ans.push_back(str[i]);
}
void solve() {
    int m;
    scanf("%d%s",&m,str+1);
    n=strlen(str+1);
    ans="";
    build();
    rk[n+1]=0;
    solve('z',1,m);
    for(auto c: ans) putchar(c);
    putchar('\n');
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        solve();
    }
    return 0;
}