941 - Permutations

/* ******************************************* */
// \_/\_/\_/\_/---Coded by Panks---\_/\_/\_/\_/ //
/* ******************************************* */


// **********************Headers******************

//C headers
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<climits>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<clocale>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>

//containers
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<complex>
#include<string>
#include<stack>
#include<bitset>
#include<istream>
#include<valarray>

//IOs
#include<iostream>
#include<sstream>
#include<iomanip>
#include<fstream>
#include<exception>
#include<ios>
#include<iosfwd>
#include<ostream>
#include<iterator>
#include<stdexcept>
#include<streambuf>

//algorithm & miscellaneous
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<limits>
#include<locale>
#include<memory>
#include<new>
/* ********************************************** */


////////////////////SHORTHANDS\\\\\\\\\\\\\\\\\\\\\

#define ull unsigned long long
#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n-1)

#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REPD(i,n) FOR(i,n-1,0)

#define testcase(t) int t;scanf("%d",&t);while(t--)
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)

#define p(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define ps(x) printf("%s",x)

#define pn(x) printf("%d\n",x)
#define pln(x) printf("%lld\n",x)
#define psn(x) printf("%s\n",x)

#define all(c) c.begin(),c.end() 
//////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\


// ---------------Fast IO using getchar-------------- \\
// will accept values 9-digits in int and 19-digits in long long on my system

int getint();
int getint(){
    int c = 'a';
    while (!(c >= '0' && c <= '9') && c != '-')
        c = getchar();
    int c2;
    if (c != '-')
        c2 = c;
    else
        c2 = '0';
    int res = 0;
    while((c2 >= '0' && c2 <= '9')){
        res = (res << 3) + (res << 1) + (c2 - '0');
        
        c2 = getchar();
    }
    return res * (c == '-' ? -1 : 1);
}
// ------------------------------------------------- \\

//------------------Actual Code--------------------- \\


using namespace std;

bool compit (char a, char b);
bool compit (char a, char b){
    return int(a)<int(b);
}

long int factorial(long int n);
long int factorial(long int n){
    int a=1;
    while (n!=1) {
        a*=n;
        n--;
    }
    return a;
}

int main(){
    
    int t;
    string input="";
    long int no, fact;
    cin>>t;
    while (t--) {
        cin>>input>>no;
        sort(all(input), compit);
        int a=0;
        fact=1;
        int long factor=factorial(input.size());
        no=no%factor;
        
        if (no!=0) {
            while (fact<=no) {
                a++;
                fact=fact*a;
            }
            fact/=a;
            a--;
            
        }else{
            fact=0;
            a=0;
            
        }
        
        string ans="";
        while (a--) {
            ans+=char(int(no/fact)+48);
            no=no%fact; 
            fact/=(a+1);
        }
        ans+='0';
        
        int long diff=input.size()-ans.size();
        if (diff<0) {
            diff=0;
        }
        while (diff--) {
            ans='0'+ans;
        }
        
        
        long int len=input.size();
        int i=0;
        len--;
        string final="";
        while (len--) {
            final+=input[ans[i]-48];
            input.erase(input.begin()+ans[i]-48);
            i++;
        }
        cout<<final+input<<endl;
        
    }
    
}