Antisymmetric Substrings

Byteasar studies certain strings of zeroes and ones. Let \(s\) be such a string. Let \(s^R\) denote the reversed string (i.e. the string read backwards), and let \(\bar{s}\) denote the string obtained from \(s\) by changing all the zeroes to ones and ones to zeroes.

A nonempty string \(s\) is called antisymmetric if for every position \(i\) (1-indexed) the \(i\)-th last character is different from the \(i\)-th character. In other words, a binary string \(s\) is antisymmetric if and only if

[ s = \overline{s}^R ]

For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not.

Given a binary string, count the number of contiguous, nonempty antisymmetric fragments. Note that different occurrences of identical substrings are counted separately.

inputFormat

The input consists of a single line containing a binary string (i.e. a string of characters '0' and '1').

outputFormat

Output a single integer – the number of contiguous nonempty antisymmetric substrings of the input string.

sample

0101

4