Shokry loves strings very much that he wants to distinguish every string he sees. So, he decided to give every string a special value, he calls it "String Value".

Consider that every character has a value corresponding to its order in the alphabetical order (A = 0, B = 1, C = 2 ... etc.). He looks at each character in the string from left to right, takes the sum of the values of all the characters, putting into consideration that every time a character appears one more time, its value increases by 1. Let’s call this sum X. And the string value is the uppercase letter corresponding to the number (X % 26) followed by the size of the string. (For more clarification, take a look at the examples).

Given a string S, calculate the string value for that string.

Input

The first line contains a single integer T (1 <= T <= 10) – the number of test cases, followed by T lines. Each line contains a string S, consisting of uppercase letters. (1 <= |S| <= 10⁵)

Output

For each test case print the answer to the problem.

Example

Input:
1
ABBCDD

Output:
M6

Note

In the first test case, the values of the characters in the string will be:

A = 0
B = 1
B = 2 (Value of B increased by one, because it appeared again)
C = 2
D = 3
D = 4 (Value of D increased by one, because it appeared again)

The sum X = 0 + 1 + 2 + 2 + 3 + 4 = 12
The letter corresponding to 12 % 26 is ‘M’. Then the String Value will be M6.