A mirror panel is described by a string of lowercase English letters. A contiguous substring is called near-symmetric if it can be turned into a palindrome by changing at most one of its characters. Equivalently, when you compare the substring's symmetric character pairs from the outside in, at most one pair may mismatch. Every actual palindrome qualifies (zero changes).
Count how many substrings (counting each starting/ending position separately, even if two substrings have equal text) are near-symmetric.
Input format
Line 1: a non-empty string of lowercase English letters.
Output format
A single integer: the number of near-symmetric substrings.
Constraints
- 1 <= length of the string <= 3000
- The string consists only of lowercase English letters (
a-z).