A legacy security system requires that a certain password string be a palindrome (read the same forwards and backwards). Given the current password s, find the minimum number of characters that must be inserted, at any positions in the string, to turn it into a palindrome. Characters already present in s may never be removed or reordered -- only new characters may be inserted.
Input format
Line 1: the string s (may be empty, producing a blank line).
s contains only lowercase English letters.
Output format
A single integer: the minimum number of character insertions needed to make s a palindrome.
Constraints
- 0 <= |s| <= 40