After solving seven problems on Timus Online Judge with a word
“palindrome” in the problem name, Misha has got an unusual ability.
Now, when he reads a word, he can mentally count the number of unique
nonempty substrings of this word that are palindromes.

Dima wants to test Misha’s new ability. He adds letters *s*_{1}, ...,
*s*_{n} to a word, letter by letter, and after every letter asks Misha, how
many different nonempty palindromes current word contains as substrings.
Which *n* numbers will Misha say, if he will never be wrong?

### Input

The only line of input contains the string *s*_{1}...*s*_{n}, where *s*_{i} are
small English letters (1 ≤ *n* ≤ 10^{5}).

### Output

Output *n* numbers separated by whitespaces, *i*-th of these numbers
must be the number of different nonempty substrings of prefix *s*_{1}...*s*_{i}
that are palindromes.

### Sample

**Problem Author: **Mikhail Rubinchik (prepared by Grigory Nazarov)

**Problem Source: **Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013