Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

En un reino muy lejano existe una costumbre muy extraña. Si el nombre del rey está compuesto por N caracteres, entonces se le exige que tenga exactamente N – 1 hijos. Pero todo no queda ahí, sino que el nombre de su primer hijo va a ser el mismo nombre que el del padre quitándole la primera letra, el nombre del segundo hijo va a ser el nombre del rey quitándole las dos primeras letras y así sucesivamente.

Ahora bien, se dice que uno de los hijos del rey puede heredar el trono si su nombre es menor lexicográficamente que el nombre de su padre. Veamos un ejemplo.

Si el nombre del rey es “acaba”, entonces va a tener 4 hijos llamados:

1. caba
2. aba
3. ba
4. a

Como se puede ver, solamente dos de sus hijos (2 y 4) van a poder heredar el trono.

Debido a que el rey quiere asegurar la permanencia de su descendencia en el trono, él quiere conocer cuántos de sus hijos son aptos para reinar después de él.

Input

La entrada contiene una cadena que representa el nombre del rey. Este nombre está compuesto solamente por letras minúsculas y su longitud va de 1 a 5 000 000 de caracteres.

Output

Se debe imprimir la cantidad de hijos del rey que pueden heredar el trono.

Sample test(s)