# 2013 Petrozavodsk, February 2

# Palindromes and Super Abilities

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**to a word, letter by letter, and after every letter asks Misha, how many different nonempty palindromes current word contains as substrings. Which

_{n}**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**are small English letters (

_{i}**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.

aba

1 2 3