Minimum Append to Form Palindrome

Fernando has been hired by Waterloo University to complete a development project. The university intends to construct a representative street of cottages for important foreign visitors and collaborators. Currently, cottages are built on one side of the street and their sequence of colors appears chaotic. To bring order, Fernando plans to append new cottages so that the entire sequence of cottage colors becomes symmetric, i.e., a palindrome.

You are given a non-empty string S consisting of lowercase letters. Each letter represents the color of a cottage. Your task is to determine the minimum number of characters that must be appended to the end of S in order to form a palindrome.

For instance, if S = ab, by appending a to the end, we obtain aba which is a palindrome. In mathematical terms, you need to find the smallest non-negative integer k such that $$S+\text{reverse}(S[0:k])$$ forms a palindrome.

inputFormat

The input consists of a single line containing a string S made up of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of characters that need to be appended to the end of S to make it a palindrome.

sample

aba

0