Shortest Palindromic Extension

Given a string s, your task is to determine the length of the shortest palindromic string that can be obtained by appending characters to the end of s.

A palindrome is a string that reads the same forward and backward. For example, a string s is a palindrome if and only if s = s[::-1].

You must compute the minimal length L such that by appending some characters (possibly none) to s, the resulting string is a palindrome. In mathematical notation, if n = |s| (i.e., the length of s), you are to find the smallest i (possibly zero) such that the string formed as s + X is a palindrome, where X is a string of length i. Then, the answer is L = n + i (note that i = 0 if s is already a palindrome).

All formulas are represented in LaTeX format when applicable. For example, the formula for the answer can be expressed as: $$L = n + i$$

inputFormat

The input is read from stdin and consists of a single line containing the string s. The string s will consist of lowercase English letters only.

For example:

aacecaaa

outputFormat

Output the length of the shortest palindromic string that can be formed by appending characters to the end of s. The output should be printed on stdout as a single integer.

For example:

9

## sample

abac

5