Description

A palindrome is a symmetric string. For any given string, by inserting some characters, it can be turned into a palindrome. The task is to find the minimum number of characters that need to be inserted to make the given string a palindrome.

For example, $\verb!Ab3bd!$ can become a palindrome after inserting $2$ characters, such as $\verb!dAb3bAd!$ or $\verb!Adb3bdA!$, but it cannot become a palindrome with fewer than $2$ insertions.

Note: This problem is case-sensitive.

Input Format

The input consists of one line containing a string.

Output Format

Output a single integer: the minimum number of inserted characters.

Ab3bd

2

Hint

Constraints

Let the length of the string be $l$.

For all testdata, $0 < l \le 1000$.

Translated by ChatGPT 5