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₁, ..., 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?

The only line of input contains the string s₁...s_n, where s_i are small English letters (1 ≤ n ≤ 10⁵).

Output n numbers separated by whitespaces, i-th of these numbers must be the number of different nonempty substrings of prefix s₁...s_i that are palindromes.