shuffled anagrams kickstart round e

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<ll>
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define pii pair<ll,ll>
#define vii vector<pii>
#define calc_fact(n) tgamma(n+1)
#define inf LONG_LONG_MAX
#define MOD 1000000007
#define mod 998244353

string solve()
{
    string s;
    cin>>s;
    ll n = s.length();
    vi freq(26);
    for(auto c:s){
        freq[c-'a']++;
        if(freq[c-'a']*2>n){
            return "IMPOSSIBLE";
        }
    }
    vector<pair<char,ll>> now;
    for(ll i=0;i<n;i++){
        now.pb({s[i],i});
    }
    sort(all(now));
    string ans(n,'a');
    for(ll i=0;i<n;i++){
        ll ind = (i + n / 2)%n;
        ans[now[i].second] = now[ind].first;
    }
    return ans;
}

signed main()
{
	FIO;

	ll t;
	cin>>t;
	for(ll i=1;i<=t;i++)
	{
	    cout<<"Case #"<<i<<": ";

	    cout<<solve()<<endl;
	}

}