题目描述

规定一个成双成对字符串的形式为$AABB$。

设字符串$aababa$，令$A=a$，$B=ba$,则可以组成$AABB$的形式，则$aababa$是成双成对字符串。

设字符串$abbaab$，则无法形成成双成对字符串。

给你一个字符串$s$,求$s$的所有子串中，成双成对字符串的数量。(子串即为连续的一段字符串，字符串本身也是自己的子串)

例如：$s$ = $aabbbb$

子串1：$aabb$满足$A=a,B=b$

子串2：$bbbb$满足$A=b,B=b$

子串3：$aabbbb$满足$A=a,B=bb$

所以答案为3

输入格式

一个字符串$s$

输出格式

所有子串中成双成对的数量

样例输入1

aabbbb

样例输出1

3

提示

字符串长度不超过$2000$