Um cadeado possui um sistema de código para ser aberto ao invés de uma chave. O cadeado contém uma sequência de rodas. Cada roda possui as 26 letras do alfabeto inglês (a..z), em ordem. Se você move uma roda para cima, a letra que ela mostra muda para a próxima letra do alfabeto (se a letra mostrada for 'z', então ela muda para 'a'). Se você move uma roda para baixo, ela muda para para a letra anterior do alfabeto (se a letra mostrada for 'a', ela muda para 'z').

Também é possível mover qualquer subsequência contígua de rodas para a mesma direção com apenas um movimento. Isso tem o mesmo efeito que mover todas as rodas da subsequência para aquela direção, mas executando apenas um movimento.

O cadeado abre quando a roda mostra uma determinada sequência de letras. Inicialmente, todas as rodas mostram a letra 'a'. Você quer saber qual o menor número de movimentos necessários para abrir o cadeado.

Entrada

A entrada contém vários casos de teste. Um caso de teste é descrito em exatamente uma linha contendo uma string não-vazia com no máximo 1000 letras minúsculas. A string representa a sequência secreta de letras que abre o cadeado.

O último caso de teste é seguido de uma linha contendo um único asterisco.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro, o menor número de movimentos que abre o cadeado.

Exemplo

Entrada:
abcxyz
abcdefghijklmnopqrstuvwxyz
aaaaaaaaa
zzzzzzzzz
zzzzbzzzz
*

Saída:
5
25
0
1
3