Migrated from Lutece 1305 Just a Magic String

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You have such a string $S$ a, every time you can copy $S$ to $T$ ,change a in $T$ to b, b to a, then add $T$ after $S$.

For example,

a

ab

abba

abbabaab

abbabaabbaababba

......

Finally you will get a infinite magic string.

Now, given a string $X$ only containing a and b, you should tell me if it appears in the magic string?

If it appears, than output the location it first appears, otherwise, output -1;

Input

A line with a string that consists only a and b and no more than $10^6$ characters.

Output

Print the position of the first occurrence of the string, or -1 if it doesn't exist.

Samples

bab

3

baab

5

aaabbb

-1

Resources

The 14th UESTC Programming Contest Preliminary