In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #11 exercise sheet]

[AED071] Alien Words

On a distant planet all possible words consist of at most 5 lowercase letters of the English alphabet: {a,b,c,…,z}. For a word to be considered valid, its letters must come in strictly ascending alphabetical order, that is, a letter can only appear after another letter if it also appears later in the alphabet.

For example, the following three words are valid: abc aep gwz

While the following three words are not: aab are cat

Each valid word is assigned an integer (the index) corresponding to its position in a list of all valid words ordered first by size and then alphabetically:

a -> 1
b -> 2
...
z -> 26
ab -> 27
ac -> 28
...
az -> 51
bc -> 52
...
vwxyz -> 83681

The Problem

Given a list of N valid words, your task is to calculate the position (the indices) of each word.

Input

The first line of input contains an integer N, indicating the number of words to consider. The following N lines each describe one valid word.

Output

The output should contain N lines. Each of these lines should indicate the word and the respective position (its index), as previously described.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

4
ade
a
ac
vwxyz

ade 399
a 1
ac 28
vwxyz 83681