1.


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 941 Permutations
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=882
*
* @author Christoph Hausmann
* @version 0.1, 12/16/2009
*
* Method : Lexicographical order generation, BigInteger
* Status : Accepted
* Runtime: 1.880
*/

import java.io.IOException;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Permutations_941 {
public static void main(String... args) throws NumberFormatException, IOException {
final Scanner scanner = new Scanner(System.in);

final int testCases = scanner.nextInt();

for(int i = 0; i < testCases; i++) {

final String s = sortString(scanner.next());

final BigInteger permNum = scanner.nextBigInteger();

System.out.println(permutation(permNum,s.toCharArray()));
}
}

private static String sortString(String s) {
final char[] chars = s.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}

public static char[] permutation(BigInteger k, char[] s) {
int n = s.length;

BigInteger factorial = BigInteger.ONE;
for(int j = 2; j <= n-1; j++) {
factorial = factorial.multiply(BigInteger.valueOf(j));
}
for(int j = 1; j <= n-1; j++) {
int tempj = k.divide(factorial).mod(BigInteger.valueOf(n + 1 - j)).intValue(); //(k/factorial) % (n + 1 - j);
char temps = s[j+tempj-1];
for(int i = j + tempj; i >= j+1; i--) {
s[i-1] = s[i-2];
}
s[j-1] = temps;
factorial = factorial.divide(BigInteger.valueOf(n-j)); // (n- j);
}
return s;
}


}