package com.company;


import java.util.*;

public class Main { //    dfs방식
    private static final Scanner sc = new Scanner(System.in);
    private static int result, maxCount;
    private static boolean[][] check;

    public static void main(String args[]) {
        int max = sc.nextInt();

        for (int i = 1; i < max+1 ; i++) {
            String number = sc.next();
            maxCount = sc.nextInt();

            check = new boolean[maxCount + 1][1000000]; // 같은 횟수이면서 같은 숫자를 탐색했는지 체크
            result = 0;

            changeNumber(number.toCharArray(), 0);
            System.out.println("#" + i + " " + result);

        }
    }
    public static void changeNumber(char[] numberChar, int nowCount){
        if (maxCount == nowCount){
            //횟수만큼 바꿨으면 결과 입려하고 종료
            result = result > getInteger(numberChar)? result : getInteger(numberChar);
            return;
        }
        int max = numberChar.length;
        for (int i = 0; i < max - 1; i++) {
            for (int j = 0; j < max ; j++) {
                char[] tempNumber = swap(numberChar, i, j); // 해당 자리 바꾼 char[] 받아오기
                if (!check[nowCount+1][getInteger(tempNumber)]) { // 같은 횟수이면서 같은 숫자를 탐색하지 않으면 탐색
                    check[nowCount+1][getInteger(tempNumber)] = true;
                    changeNumber(tempNumber, nowCount+1);
                }
            }
        }
    }

    public static int getInteger(char[] numberChar) {
        return Integer.valueOf(String.valueOf(numberChar));
    }

    public static char[] swap (char[] numberChar, int point1, int point2){ //해당 자리의 숫자 바꾸기
        char[] tempNumber = numberChar.clone();
        char num = tempNumber[point1];
        tempNumber[point1] = tempNumber[point2];
        tempNumber[point2] = num;
        return tempNumber;

    }
}