Minimum Insertions to Form a Palindrome

Given a string ( s ), determine the minimum number of insertions required to transform ( s ) into a palindrome.

A palindrome is a string that reads the same forwards and backwards. To solve this problem, consider finding the longest common subsequence (LCS) between ( s ) and its reverse ( s^{\text{rev}} ). The minimal number of insertions needed is given by:
[ |s| - \text{LCS}(s, s^{\text{rev}}) ] where (|s|) is the length of the string.

inputFormat

Input is read from standard input (stdin) and consists of a single line containing the string ( s ).

outputFormat

Output the minimum number of insertions required to transform the given string into a palindrome. The answer should be printed to standard output (stdout).## sample

ab

1