hoanvi6 - Tìm hoán vị thứ n của xâu

Cho một xâu, ta có thể hoán vị các kí tự để tạo thành một xâu mới. Đầu tiên, ta sắp xếp thứ tự các kí tự này theo bảng chữ cái. Sau đó ta bắt đầu hoán vị chúng

Ví dụ, xâu "abba" sẽ cho 6 hoán vị phân biệt theo thứ tự từ điển đó là:

aabb 1

abab 2

abba 3

baab 4

baba 5

bbaa 6

Cho một xâu, bàn phải tìm hoán vị thứ n của xâu đó. Trong trường hợp trên thì  'aabb' có số thứ tự là 1 và  'baab' có số thứ tự là 4

Input

Dòng đầu tiên gồm số nguyên T (≤ 200), biểu thị số test

Mỗi trường hợp chỉ chứa một xâu khác rỗng khác kí tự in thường, với chiều dài không quá 20, và một số nguyên n (0<n<2^31) biểu thị hoán vị thứ n ta cần tìm

Output

Vỡi mỗi trường hợp, đưa ra hoán vị thứ n. Nếu hoán vị thứ n không tồn tại, ta đưa ra Impossible