Minimum Characters to Append for Symmetry

You are given a string (s). Your task is to determine the minimum number of characters that must be appended to the end of (s) to make it symmetric (i.e., a palindrome). A string is symmetric if it reads the same forward and backward.

For example, for the string (s = \texttt{abcd}), appending (\texttt{abc}) results in (\texttt{abcdcba}), which is symmetric. Formally, if (n = |s|), find the smallest non-negative integer (k) such that if we append (s[0:k]) in reverse order to (s), the resulting string becomes a palindrome. Equivalently, determine the minimum (k) such that (s[i:]) is a palindrome for some (0 \le i \le n).

Use efficient string algorithms to solve this problem as the input size could be large.

inputFormat

The input consists of a single line containing the string (s). The string may be empty and will consist of ASCII characters.

outputFormat

Output a single integer representing the minimum number of characters that must be appended to (s) to make it symmetric.## sample

radar

0