삼성 Expert 1244 최대 상금

ans = 0
 
 
def dfs(count):
    global ans
 
    temp = int(''.join(ar))
 
    if count == 0:
        ans = max(ans, temp)
 
        return
 
    for i in range(len(ar)):
        for j in range(i + 1, len(ar)):
            ar[i], ar[j] = ar[j], ar[i]
 
            temp_key = ''.join(ar)
 
            if chk.get((temp_key, count - 1), 1):
                chk[(temp_key, count - 1)] = 0
                dfs(count - 1)
 
            ar[i], ar[j] = ar[j], ar[i]
 
 
for test_case in range(1, int(input()) + 1):
    ans = 0
 
    ar, n = input().split()
    ar = list(ar)
    n = int(n)
 
    chk = {}
 
    dfs(n)
 
    print(f'#{test_case} {ans}')