#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main(){
	//快读可根据需求自行添加（本题时限为2、3秒）。
	cin>>t;
	for(int tt=1;tt<=t;tt++){
		cin>>s;
		int pre=0,flag=-1,x;//pre记录上一位数，falg判断是否非递增。
		priority_queue<int,vector<int>,greater<int> >q,q1;//优先队列。
		for(int i=s.size()-1;i>=0;i--){
			if((s[i]-'0')>=pre){//大于或等于上一个数，入队。
				q.push(s[i]-'0');
				pre=s[i]-'0';//更新上一个。
			}else{
				flag=i;//第2中情况。
				while(!q.empty()){//找第一个大于s[i]-'0'的数。
					if(q.top()<=(s[i]-'0')){
						q1.push(q.top());//q1为辅助数组。
						q.pop();
					}else{
						x=q.top();
						q.pop();
						break;
					}
				}while(!q1.empty()){
					q.push(q1.top());
					q1.pop();
				}
				q.push(s[i]-'0');
				break;
			}
		}
		cout<<"Case #"<<tt<<": ";//标准格式。
		if(flag!=-1){//情况一。
			if(flag)cout<<s.substr(0,flag)<<x;
			else cout<<x;
			while(!q.empty()){
				cout<<q.top();
				q.pop();
			}
		}else{//情况二。
			int ans=1;
			while(!q.empty()){
				if(q.top()==0){
					ans++;
					q.pop();
				}else{
					cout<<q.top();
					q.pop();
					break;
				}
			}while(ans--){
				cout<<"0";
			}while(!q.empty()){
				cout<<q.top();
				q.pop();
			}
		}
		cout<<"\n";
	}
	return 0;//好习惯。
}