Ancient Palindromic Seed Codes

The archaeologists on planet X have discovered a series of ancient codes, formed by sequences of seeds from four types of plants: A, B, C, and D. Detailed analysis suggests that these codes were originally palindromic (i.e. they read the same forwards and backwards). However, due to the passage of time, many of the seeds have fallen off, possibly breaking the mirror symmetry.

Your task is: Given the current code (a sequence of characters from {A, B, C, D}), determine the minimum number of seeds that must have been lost from the original palindromic sequence in order for it to appear as the given sequence.

Explanation: The original palindromic sequence can be thought of as a supersequence of the given code. You need to compute the shortest palindrome that has the given sequence as a subsequence. The number of dropped seeds is the difference between the length of this palindrome and the length of the given sequence. Mathematically, if the length of the longest palindromic subsequence (LPS) in the given sequence is L, the answer is given by:

\[ \text{Answer} = |S| - L \]

where \(|S|\) is the length of the given sequence. This is equivalent to the minimum number of insertions required to convert the string into a palindrome.

inputFormat

The input consists of a single line containing a non-empty string S, which only contains the uppercase characters A, B, C, and D. The length of S is at most 1000.

outputFormat

Output a single integer: the minimum number of seeds that must have been dropped from the original palindromic code.

sample

ABA

0