#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    string s;cin>>s;
    int n=s.size();
    int cntA=count(s.begin(),s.end(),'A');
    int cntC=count(s.begin(),s.end(),'C');
    int cntK=count(s.begin(),s.end(),'K');
    if(max({cntA,cntC,cntK})>(n+1)/2){cout<<"Impossible!";return 0;}
    vector<int> posA,posC,posK;
    for(int i=0;i<n;i++){
        if(s[i]=='A')posA.push_back(i);
        else if(s[i]=='C')posC.push_back(i);
        else posK.push_back(i);
    }
    vector<vector<vector<vector<ll>>>> dp(cntA+1,vector<vector<vector<ll>>>(cntC+1,vector<vector<ll>>(cntK+1,vector<ll>(3,INF))));
    if(cntA>0)dp[1][0][0][0]=0;
    if(cntC>0)dp[0][1][0][1]=0;
    if(cntK>0)dp[0][0][1][2]=0;
    for(int len=1;len<n;len++){
        for(int a=0;a<=cntA;a++){
            for(int c=0;c<=cntC;c++){
                int k=len-a-c;
                if(k<0||k>cntK)continue;
                for(int last=0;last<3;last++){
                    if(dp[a][c][k][last]==INF)continue;
                    if(last!=0&&a<cntA){
                        int p=posA[a];
                        ll cost=(c-(upper_bound(posC.begin(),posC.begin()+c,p)-posC.begin()))+(k-(upper_bound(posK.begin(),posK.begin()+k,p)-posK.begin()));
                        dp[a+1][c][k][0]=min(dp[a+1][c][k][0],dp[a][c][k][last]+cost);
                    }
                    if(last!=1&&c<cntC){
                        int p=posC[c];
                        ll cost=(a-(upper_bound(posA.begin(),posA.begin()+a,p)-posA.begin()))+(k-(upper_bound(posK.begin(),posK.begin()+k,p)-posK.begin()));
                        dp[a][c+1][k][1]=min(dp[a][c+1][k][1],dp[a][c][k][last]+cost);
                    }
                    if(last!=2&&k<cntK){
                        int p=posK[k];
                        ll cost=(a-(upper_bound(posA.begin(),posA.begin()+a,p)-posA.begin()))+(c-(upper_bound(posC.begin(),posC.begin()+c,p)-posC.begin()));
                        dp[a][c][k+1][2]=min(dp[a][c][k+1][2],dp[a][c][k][last]+cost);
                    }
                }
            }
        }
    }
    ll ans=min({dp[cntA][cntC][cntK][0],dp[cntA][cntC][cntK][1],dp[cntA][cntC][cntK][2]});
    if(ans>=INF)cout<<"Impossible!";
    else cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    string s;cin>>s;
    int n=s.size();
    int cntA=count(s.begin(),s.end(),'A');
    int cntC=count(s.begin(),s.end(),'C');
    int cntK=count(s.begin(),s.end(),'K');
    if(max({cntA,cntC,cntK})>(n+1)/2){cout<<"Impossible!";return 0;}
    vector<int> posA,posC,posK;
    for(int i=0;i<n;i++){
        if(s[i]=='A')posA.push_back(i);
        else if(s[i]=='C')posC.push_back(i);
        else posK.push_back(i);
    }
    vector<vector<vector<vector<ll>>>> dp(cntA+1,vector<vector<vector<ll>>>(cntC+1,vector<vector<ll>>(cntK+1,vector<ll>(3,INF))));
    if(cntA>0)dp[1][0][0][0]=0;
    if(cntC>0)dp[0][1][0][1]=0;
    if(cntK>0)dp[0][0][1][2]=0;
    for(int len=1;len<n;len++){
        for(int a=0;a<=cntA;a++){
            for(int c=0;c<=cntC;c++){
                int k=len-a-c;
                if(k<0||k>cntK)continue;
                for(int last=0;last<3;last++){
                    if(dp[a][c][k][last]==INF)continue;
                    if(last!=0&&a<cntA){
                        int p=posA[a];
                        ll cost=(c-(upper_bound(posC.begin(),posC.begin()+c,p)-posC.begin()))+(k-(upper_bound(posK.begin(),posK.begin()+k,p)-posK.begin()));
                        dp[a+1][c][k][0]=min(dp[a+1][c][k][0],dp[a][c][k][last]+cost);
                    }
                    if(last!=1&&c<cntC){
                        int p=posC[c];
                        ll cost=(a-(upper_bound(posA.begin(),posA.begin()+a,p)-posA.begin()))+(k-(upper_bound(posK.begin(),posK.begin()+k,p)-posK.begin()));
                        dp[a][c+1][k][1]=min(dp[a][c+1][k][1],dp[a][c][k][last]+cost);
                    }
                    if(last!=2&&k<cntK){
                        int p=posK[k];
                        ll cost=(a-(upper_bound(posA.begin(),posA.begin()+a,p)-posA.begin()))+(c-(upper_bound(posC.begin(),posC.begin()+c,p)-posC.begin()));
                        dp[a][c][k+1][2]=min(dp[a][c][k+1][2],dp[a][c][k][last]+cost);
                    }
                }
            }
        }
    }
    ll ans=min({dp[cntA][cntC][cntK][0],dp[cntA][cntC][cntK][1],dp[cntA][cntC][cntK][2]});
    if(ans>=INF)cout<<"Impossible!";
    else cout<<ans;
    return 0;
}

https://vijos.org/d/wjszez/records/6a083d246e95524834d3e7f4