Un hecho poco conocido de las vacas es que ellas tienen su versión propia del alfabeto, el "vacalfabeto". Consiste de las 26 letras de 'a' a 'z', pero cuando una vaca recita el vacalfabeto, ella lista esas letras en un ordenamiento específico que podría ser diferente del orden 'abcdefghijklmnopqrstuvwxyz' al cual estamos acostumbrados a oir.

Para pasar el tiempo, Mildred la prima de Bessie ha estado recitando el vacalfabeto una y otra vez, y el Granjero Juan quiere saber cuántas veces lo ha recitado.

Dada una cadena de letras minúsculas que el Granjero Juan ha oido decir a Mildred, calcule el número mínimo de veces que Mildred ha recitado tod el vacalfabeto para que el Granjero Juan haya oido la cadena dada. El Granjero Juan no está siempre poniendo atención a lo que Mildred recita, y por lo tanto él podría habe perdido algunas de las letras que Mildred ha recitado. La cadena que se le da a usted consiste de exactamente de las letras que él recuerda haber oido.

Nota: el tiempo límite por caso de prueba en este problema es el dobel del de por defecto.

Entrada

La única línea de la entrada contiene la cadena de letras en minúsculas que el Granjero Juan ha odio decir a Mildred. Esta cadena tiene longitud 1 y a lo más ~10^5~.

Salida

Imprima el mínimo número de veces que Mildred debe haber recitado todo el vacalfabeto.

Ejemplo de Entrada

mildredree

Ejemplo de Salida

3

Mildred debe haber recitado el vacalfabeto al menos tres veces. Es posible que Mildred haya recitado solamente el vacalfabeto tres veces si el vacalfabeto comienca con "mildre" y el Granjero Juan oyó las letras en mayúscula mostradas abajo.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

USACO 2021 January Contest, Gold Problem 1. Uddered but not Herd.