One-Dimensional Elimination Game

You are given a string s of length \(n\) consisting only of lowercase letters. In this game, an operation consists of deleting two adjacent characters if and only if they are identical. A string is called eliminable if by applying this operation repeatedly, it can be reduced to an empty string.

Your task is to count how many non-empty contiguous substrings of s are eliminable.

For example, consider the string "abba":

• The substring "bb" is eliminable because the two letters are the same.
• The substring "abba" is eliminable since:
  \(abba \to aa\) (by removing the middle "bb") and then \(aa \to \varepsilon\) (by removing "aa").

Note: The elimination operation is defined as follows: if for any position \(i\), \(s_i = s_{i+1}\), then you can remove both characters, and the remaining parts of the string are concatenated together. In latex format, the rule is: if \(s_i = s_{i+1}\), then \(s = s_1s_2\cdots s_{i-1}\, s_{i+2}\cdots s_n\).

inputFormat

The input consists of a single line containing a string s of length \(n\) (\(1 \le n\le 50\)) composed of lowercase letters.

outputFormat

Output a single integer, which is the number of non-empty contiguous substrings of s that are eliminable.

sample

abba

2