A substring of a string S is a contiguous sequence of characters within S. The prefix of a string S is a substring that includes the first character of S. The suffix of a string S is a substring that includes the last character of S.

Consider the string “qualification”. The strings “fat” or “lion” are not its substrings, because the characters of these strings do not go in it one after another. “cat” and “alif” are substrings but they both are neither a prefix nor a suffix. “qual” is a prefix and “cation” is a suffix. The string “qualification” is both a prefix and a suffix of itself.

In this problem the characters in strings are indexed from zero.

A period of a string S is the minimum positive integer T such that for any 0 ≤ i < |S| it is true that S[i] = S[i mod T], where i mod T is the remainder of the division of i by T.

A border of a string S is a non-empty prefix that is not equal to string S and equal to its suffix. A complexity of a string is the number of different periods of its borders. A dynamic complexity of a string is the sum of complexities of all its prefixes.

For a given binary string S and for each integer i from 1 to 25 you should find a binary string of length |S| + i, where the string S is a prefix, such that its dynamic complexity is the maximal possible.

The single line contains a binary string S, 0 ≤ |S| ≤ 10⁵, that consists only of characters {X, .}.

For each i from 1 to 25 you have to output the maximal dynamic complexity of a string S + T, where |T| = i.