Given a string, you may insert new characters at any positions (front, back, or between existing characters). Determine the minimum number of insertions needed so that the string becomes a palindrome (reads the same forwards and backwards). You only need the minimum count, not the resulting palindrome, so the answer is unique.
For example, ab needs one insertion (insert a at the end to get aba, or b at the front to get bab), so the answer is 1. A string that is already a palindrome needs 0 insertions.
Input format
A single line containing the string, made up of lowercase English letters.
Output format
A single integer: the minimum number of character insertions required to turn the input into a palindrome.
Constraints
- The string length n satisfies 1 <= n <= 1000.
- The string contains only lowercase letters
a-z.