#include <bits/stdc++.h>
using namespace std;
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
string solve(string s){
    bool flag=false;
    int n=s.size();
    for (int i=n-2;i>=0;i--){
        if (s[i]<s[i+1]){
            flag=true;
            int j=n-1;
            while (s[j]<=s[i]){
                j--;
            }
            swap(s[i],s[j]);
            reverse(s.begin()+i+1,s.end());
            break;
        }
    }
    if (!flag){
        sort(s.begin(),s.end());
        int pre=0;
        while (pre<s.size() && s[pre]=='0') pre++;
        if (pre<s.size()){
            swap(s[0],s[pre]);
            sort(s.begin()+1,s.end());
        }
    }
    return s;
}
int main(){
    int T,i=1;
    T=read();
    while (T--){
        string n;
        cin>>n;
        cout<<"Case #"<<i<<": "<<solve(n)<<endl;
        i++;
    }
    return 0;
}