Minimum Deletions to Form a Palindrome

You are given a string \( s \) consisting of lowercase English letters. Your task is to determine the minimum number of characters that must be removed from \( s \) in order to make it a palindrome. A palindrome is a string that reads the same forwards and backwards.

You can solve this problem by finding the longest palindromic subsequence (LPS) of \( s \) and then subtracting its length from the length of \( s \). In mathematical form:

\[ \text{min_deletions} = |s| - \text{LPS}(s) \]

Carefully implement your solution so that it reads input from standard input and writes output to standard output.

inputFormat

The input consists of a single line containing the string \( s \). The string \( s \) is composed of lowercase English letters only.

outputFormat

Output a single integer which represents the minimum number of deletions required to transform \( s \) into a palindrome.

## sample

abac

1