Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 22 de Novembro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #06]

[DAA 023] Palavras numeradas

Esquemas de codificação são muitas vezes usados em situações que precisam de reduzir os custos de armazenamento ou transmissão de mensagens. Neste problema, vamos usar um esquema de codificação muito simples que associa um inteiro a um conjunto restrito de palavras de 5 ou menos letras.

Considere o alfabeto inglês com 26 letras: {a, b, c, ..., z}. Uma palavra é considerada válida se tiver entre 1 a 5 letras minúsculas deste alfabeto e se letras consecutivas da palavra estão por ordem alfabética estritamente crescente (ou seja, letras que aparecem depois numa palavra, também devem aparecer depois na lista ordenada de letras do alfabeto).

Por exemplo, as seguintes palavras são válidas:

abc aep gwx abcde z oq bgkm

Já as palavras seguintes não são válidas:

abb are cat dc bcdea

A cada palavra válida é associada um número inteiro indicando a posição da palavra na lista ordenada de palavras válidas (as palavras vêm por ordem crescente de tamanho, e em caso de empate por ordem alfabética), ou seja:

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

O Problema

Dado um conjunto de palavras com 5 ou menos letras, a tua tarefa é descobrir se a palavra é válida (segundo os critérios atrás definidos) e em caso afirmativo indicar qual a sua posição na lista ordenada atrás descrita.

Input

Na primeira linha do input vem um número N indicando qual a quantidade de palavras. Seguem-se N linhas, cada uma contendo uma palavra constituída por 1 a 5 letras minúsculas do alfabeto inglês {a, b, c, ..., z}.

Output

O output deve ter exactamente N linhas. A i-ésima linha deve indicar 0 se a i-esima palavra do input não for válida ou um inteiro entre 1 e 83861 indicando a posição da palavra na lista ordenada.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Exemplo de Input

9
z
a
daa
vwxyz
dhiz
rtw
rtp
aaaaa
abcde

Exemplo de Output

26
1
0
83681
9634
2877
0
0
17902

Explicação do Input/Output

• "z" é a 26ª palavra
• "a" é a 1ª palavra
• "daa" não é uma palavra válida
• "vwxyz" é a 83681ª palavra
• "dhiz" é a 9634ª palavra
• "rtw" é a 2877ª palavra
• "rtp" não é uma palavra válida
• "aaaaa" não é uma palavra válida
• "abcde" é a 17902ª palavra

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto