PALINDROME

Interview

Time limit1sMemory limit1024 MB

Summary

Given a non-palindrome string, find the minimum length after prepending letters to make it a palindrome.

Level: Medium5 of 10
Topics: String, String matching, Two pointers, Hash map
Solved: No attempts yet

Problem

You are given a string of lowercase Latin letters that is not a palindrome. You append several lowercase Latin letters (1, 2, ...) to the left of the string so that the resulting string is a palindrome. Write a program palin that prints the smallest possible length of the resulting string.

Note: a string is called a palindrome if it reads the same left to right and right to left.

Input

A string of length N made of lowercase Latin letters.

Output

A single integer equal to the required minimum length.

Constraints

0 < N < 500 000

Examples1

Example 1
Input
```
babaa
```
Expected output
```
7
```