A mural strip is described by a string of lowercase letters. You may insert new characters at any positions. Find the minimum number of insertions required to make the whole string a palindrome (a string that reads the same forwards and backwards).
Input format
Line 1: the strip string s.
Output format
A single integer: the minimum number of insertions to make s a palindrome.
Constraints
- 1 <= length of
s<= 40 sconsists of lowercase English letters only.