该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

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

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

对于另外 $40\%$ 的数据：$|S| \leq 100$。

样例输入1

ACAKA

样例输出1

0

样例输入2

AACKK

样例输出2

2

样例解释2

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

样例输入3

AAAAKKKAKAKCKCKAKAKCACAKCAKAAKCACCAKCAAAKCAKCK

样例输出3

12