Description

对一个AB串，进行一定的操作，每次操作只能交换相邻的字符。求最少的操作数使得相同的字母都在同一边，如AAAAABBBBB。

Input

每一行给出一个AB串，长度不超过100，且A、B都含有，不含其它字符

Output

每一行一个答案，输出最少操作次数。

Sample

Input

ABA

Output

1

Source: 李广为