Description

Best of N (BON) is a multi-round competition mechanism where two players compete for up to $N$ rounds, and the first side to win more than half of the $N$ rounds is declared the winner. For example, a common badminton match is BO3, while in games like League of Legends (LOL), there are formats like BO1 (a single decisive round), BO3, BO5, and so on. Please note that the value of $N$ must always be an odd integer.

Now, teams A and B have participated in a match under the BO$x$ format for $m$ rounds. The outcomes of the rounds are represented by a string of length $m$, consisting only of the letters A and B. If the $i$-th character is A, it means that Team A won that round; otherwise, Team B won. If there exists an $x$ such that the current state represents the outcome of a concluded BO$x$ format match, output $x$; otherwise, output $-1$.

Input

The only line contains one string $s$ of length $m\ (1\le m\le 10^5)$, representing the outcomes of each round. It's guaranteed that the string only contains the letters A and B.

Output

If the match has concluded, output the value of $x$. Otherwise, output $-1$.

Samples

ABBAA

5

AAB

-1

Note

For the first example, Team A won Team B by $3:2$. So it's a BO5 match.

For the second example, the match is not concluded. So output $-1$.

Resources

电子科技大学第十四届 ACM 趣味程序设计竞赛