SPOJ Brasil

Sua escola possui um computador que é usado como um servidor web para hospedar a página da instituição, páginas pessoais, páginas de grupos de pesquisas e muitas outras coisas.

Recentemente, o disco rídigo foi corrompido, portanto a organização de todos os arquivos foi perdida. Infelizmente, não há backup da informação. A única esperança é olhar todas as informações do disco e tentar descobrir quais partes pertencem a cada arquivo. Felizmente, o disco estava usando um sistema de arquivos que guardava cada arquivo individual de forma contígua, portanto somente partes contíguas das informações devem ser inspecionadas.

As informações do disco são uma sequência de bytes. Cada byte nesse disco pode armazenar uma letra do alfabeto inglês (distinguindo entre maísculas e minúsculas), um dígito decimal, um ponto ou uma vírgula, totalizando 64 diferentes caracteres.

Enquanto você estava pensando como resolver este problema, você repentinamente lembrou que o sistema de arquivos também mantinha múltiplas cópias de cada arquivo, assim apenas partes de bytes contíguos que são repetidos possuem uma chance de ser um arquivo. Além disso, para cada repetição dos mesmos bytes contíguos, apenas uma cópia precisa ser verificada. Por exemplo, se a informação é ababcabb, as sequências contíguas a, b e ab sao repetidas, mas nada contendo c, ba nem bb é. Desta forma, temos 3 blocos de bytes contíguos que devem ser checados.

Você decidiu escrever um programa que calcula exatamente quantas sequências devem ser verificadas, ou seja, o número de sequências de bytes contíguas e distintas que aparecem ao menos duas vezes no disco rígido.

Entrada

A entrada possui vários casos de teste. Cada caso de teste é dado em exatamente uma linha contendo uma string não-vazia de no máximo 10⁵ caracteres representando as informações no disco rígido. Cada caractere na string é uma letra minúscula, uma letra maiúscula, um dígito, um ponto ou uma vírgula.

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

Saída

Para cada caso de teste, imprima uma única linha contendo um único inteiro, o número de subsequências contíguas distintas que aparecem ao menos duas vezes na entrada.

Exemplo

Entrada:
ababcabb
mississippi
aaaaaaaaaaaaaaaaaaaaaaaaaa
012345678,abcdefg.STUVWXYZ
say.twice,say.twice
*

Saída:
3
9
25
0
45