#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(ll t) {
string s;
cin >> s;
vector<int> v(26);
for (int i = 0; i < s.length(); i++) {
v[s[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (v[i] > s.length() / 2) {
cout << "Case #" << i << ": IMPOSSIBLE" << endl;
return;
}
}
string ans;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < 26; j++) {
if (v[j] > 0 and s[i] - 'a' != j) {
string k {'a' + j};
ans += k;
v[j]--;
break;
}
}
}
cout << "Case #" << t << ": " << ans << endl;
}
int main() {
ll t;
cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKdm9pZCBzb2x2ZShsbCB0KSB7CglzdHJpbmcgczsKCQoJY2luID4+IHM7Cgl2ZWN0b3I8aW50PiB2KDI2KTsKCWZvciAoaW50IGkgPSAwOyBpIDwgcy5sZW5ndGgoKTsgaSsrKSB7CgkJdltzW2ldIC0gJ2EnXSsrOwoJfQoJCglmb3IgKGludCBpID0gMDsgaSA8IDI2OyBpKyspIHsKCQlpZiAodltpXSA+IHMubGVuZ3RoKCkgLyAyKSB7CgkJCWNvdXQgPDwgIkNhc2UgIyIgPDwgaSA8PCAiOiBJTVBPU1NJQkxFIiA8PCBlbmRsOwoJCQlyZXR1cm47CgkJfQoJfQoJc3RyaW5nIGFuczsKCWZvciAoaW50IGkgPSAwOyBpIDwgcy5sZW5ndGgoKTsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPCAyNjsgaisrKSB7CgkJCWlmICh2W2pdID4gMCBhbmQgc1tpXSAtICdhJyAhPSBqKSB7CgkJCQlzdHJpbmcgayB7J2EnICsgan07CgkJCQlhbnMgKz0gazsKCQkJCXZbal0tLTsKCQkJCWJyZWFrOwoJCQl9CgkJfQoJfQoJY291dCA8PCAiQ2FzZSAjIiA8PCB0IDw8ICI6ICIgPDwgYW5zIDw8IGVuZGw7Cn0KCgppbnQgbWFpbigpIHsKCWxsIHQ7CgljaW4gPj4gdDsKCQoJZm9yIChpbnQgaSA9IDE7IGkgPD0gdDsgaSsrKSB7CgkJc29sdmUoaSk7Cgl9CglyZXR1cm4gMDsKfQ==