403232: GYM101086 D Secure but True

Since both Nicole and Noura are admins for the ACPC page, they need to agree on a secure and easy way to exchange password information whenever one of the admins changes it, therefore, Nicole suggested the following technique for doing it:

Let L be the list of all strings that contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y}, sorted by their length. If two strings have the same length, they are sorted according to the alphabetical order.

Help Nicole and Noura by writing a program that finds the new password. Given a string S that contains only mirrored letters, the new password is the string in L that is located after the string S by K.

The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.

Each test case will consist of an integer K (1 ≤ K ≤ 10⁹), followed by the string S (1 ≤ |S| ≤ 10³).

|S| represents the length of the string S.

For each test case, print the new password on a single line.

4
2 M
4577 ATM
491 AI
132 A

T
ITMO
MAX
AAA

Warning: large Input/Output data, be careful with certain languages.