D. Secure but True
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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 ≤ 109), followed by the string S (1 ≤ |S| ≤ 103).

|S| represents the length of the string S.

Output

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

Examples
Input
4
2 M
4577 ATM
491 AI
132 A
Output
T
ITMO
MAX
AAA
Note

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