Raízes de strings

Na matemática, a $N$-ésima raiz de um número $M$ é um número $K$ tal que $K^N = M$, isto é, $KKK\ldots K = m$, onde $K$ é multiplicado $N$ vezes.

Podemos transpor este conceito para strings. Em notação de strings, a justaposição significa concatenação, ao invés de multiplicação. Deste modo, a raiz $N$-ésima da string $S$ é uma string $T$ tal que $T^N = S$, onde $T^N = TTT\ldots T$ é a string $T$ concatenada $N$ vezes.

Por exemplo, se $S$ = “abcabcabcabc”, para $N = 2$ a string $T$ = “abcabc” é a raiz $N$-ésima de $S$, enquanto que para $N = 4$, a $N$-ésima raiz é $T$ = “abc”. Note que, para $N = 1$, qualquer string $S$ é a raiz $N$-ésima de si mesma.

Dada uma string $S$, você deve encontrar o maior valor de $N$ tal que a raiz $N$-ésima de $S$ existe. No exemplo dado, a resposta seria 4, uma vez que não existe a raiz $N$-ésima de $S$ para $N > 4$.

Entrada

A entrada consiste em vários casos de teste, cada um descrito em uma única linha.

Cada caso de teste contém uma string $S$, não vazia, com, no máximo, $10^5$ caracteres dentre dígitos decimais e caracteres alfabéticos minúsculos.

A última linha da encontra contém um único asterisco (“*”), o qual não deve ser processado como um caso de teste.

Saída

Para cada caso de teste imprima uma única linha, com o maior inteiro $N$ tal que existe uma string $T$ tal que, quando concatenada consigo mesma $N$ vezes, resulta em $S$.

Exemplo de Entrada 1

abcabcabcabc
abcdefgh012
aaaaaaaaaa
*

Exemplo de Saída 1

4
1
10