题目描述

众所周知，在平时刷题的时候，AC 代表了快乐，而 AK 代表了加倍快乐！

随着不断地刷题，徐老师越发地喜欢 AC、AK 这两个词了。

于是有一天他在发呆的时候，发现自己无意识地在纸上写下了一排 AC、AK！

但是由于徐老师是在发呆的时候写的，所以这一排字母中的 A、C、K 的数量和位置是随机的。

徐老师觉得这样的序列并不快乐，他想用序列组成很多的 AC、AK，但是他太菜了，没有办法实现，并且他也不会用这个问题难为你。

于是徐老师简化了一下要求，他现在只希望不要出现相邻的 AA、CC、KK 就可以了。

现在徐老师想知道，他最少经过几次交换才可以满足他的要求？

徐老师每次只能交换两个相邻的字母。

输入格式

本题采用文件读写。

• 读入文件名：AC.in
• 写出文件名：AC.out

第一行包含一个字符串 $S$，保证仅包含 A、C、K 三个字母。

输出格式

输出一个整数，表示最少的操作次数。若不可能满足徐老师的要求，则输出 Impossible!。

样例

ACAKA

0

AACKK

2

AAAAKKKAKAKCKCKAKAKCACAKCAKAAKCACCAKCAAAKCAKCK

12

样例说明

对于样例 2：

第一步交换后为 ACAKK；第二步交换后为 ACKAK。

数据范围与提示

• 对于 $30\%$ 的数据，$|S|\le12$。
• 对于另外 $30\%$ 的数据，其中一个字母的数量大于 $\lfloor |S|/2\rfloor$。
• 对于 $100\%$ 的数据，$|S|\le400$。