Một hoán vị của một xâu là tập hợp tất cả các cách kết hợp các ký tự của nó. Ví dụ, hoán vị của "abc" là {"abc", "acb", "bac", "bca", "cab", "cba"}. Kích thước của tập này là giai thừa của độ dài xâu ban đầu.

Cho một xâu S (độ dài tối đa 20 ký tự, gồm các chữ cái thường) và một số nguyên N \((0 \le N \lt 20!)\), hãy tìm phần tử nhỏ thứ \((N+1)\) trong tập hoán vị của S (theo thứ tự từ điển; ví dụ hoán vị của "abc" được biểu diễn theo thứ tự từ điển từ trái sang phải).

Ví dụ:

• Nếu S = "abc" và N = 0 thì kết quả là "abc"
• Nếu S = "abc" và N = 5 thì kết quả là "cba"
• Nếu S = "abc" và N = 3 thì kết quả là "bca"
• Nếu S = "cba" và N = 3 thì kết quả là "bca"

Lưu ý rằng xâu ban đầu có thể không được sắp xếp (xem hai ví dụ cuối).

Đầu vào

Tập tin đầu vào chứa một dòng với số lượng bộ dữ liệu, sau đó mỗi bộ dữ liệu gồm hai dòng:

1. Dòng đầu chứa xâu S
2. Dòng tiếp theo chứa số N

Đầu ra

• Với mỗi bộ dữ liệu, in ra một dòng chứa giá trị yêu cầu.

Input

2
abc
3
abcde
119

Output

bca
edcba