Minimum Insertions to Form a Palindrome

You are given a string s consisting of lowercase English letters. Your task is to 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. The solution is based on finding the longest palindromic subsequence (LPS) of s and using the relation:

$$\text{minInsertions}(s) = |s| - LPS(s)$$

where |s| denotes the length of s and LPS(s) can be computed as the longest common subsequence between s and its reverse.

inputFormat

The input consists of a single line containing a non-empty string s made up of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of insertions required to make s a palindrome.

## sample

abc

2

</p>