Make a Palindrome

Interview

Time limit2sMemory limit128 MB

Summary

Given a lowercase string of length at most 50, find the minimum length of a palindrome obtained by appending characters only to its end.

Level: Easy3 of 10
Topics: String, Brute force, Two pointers
Solved: No attempts yet

Problem

You are given a string S. Append zero or more characters to the end of S so that the whole string becomes a palindrome. A palindrome reads the same from left to right and from right to left.

Find the length of the shortest palindrome that can be made this way.

Input

The first line contains the string S. S consists only of lowercase English letters, and its length is at most 50.

Output

Print the length of the shortest palindrome that can be made by appending zero or more characters to the end of the string.

Examples4

Example 1
Input
```
abab
```
Expected output
```
5
```
Example 2
Input
```
abacaba
```
Expected output
```
7
```
Example 3
Input
```
qwerty
```
Expected output
```
11
```
Example 4
Input
```
abdfhdyrbdbsdfghjkllkjhgfds
```
Expected output
```
38
```