题目描述

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

随着不断的刷题，Sam 越发的喜欢 $AC,AK$ 这两个词了。

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

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

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

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

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

P.S. Sam 每次只能交换两个相邻的字母。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

ACAKA

输出 #1

0

输入输出样例 #2

输入 #2

AACKK

输出 #2

2

输入输出样例 #3

输入 #3

AAAAKKKAKAKCKCKAKAKCACAKCAKAAKCACCAKCAAAKCAKCK

输出 #3

12

说明/提示

数据范围

对于 $30\%$ 的数据：$|S| \leq 12$。

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

对于 $100\%$ 的数据：$|S| \leq 400$。

样例解释2

第一步交换后：ACAKK。 第二步交换后：ACKAK。