lightoj 1396

#include <bits/stdc++.h>
using namespace std;
char c_string[100007];
int len;
string str,c1,c2,c3,c4,res;

int main(){
    int line,cases=1,i,j;
    scanf("%d",&line);
    while(line--){
        scanf("%s",c_string);
         string str(c_string);
         printf("Case %d: ",cases++);
         //cout<<str<<endl;
         //printf("Case %d: ",cases++);
         len = str.size();
         if(str=="9") printf("11\n");
         else if(str=="99") printf("101\n");
         else if(len&1) {
              int s1,s2,a;
              c1 =  str.substr(0,len/2),c2 = c1;
              //cout<<c1<<" "<<c2<<endl;
              reverse(c2.begin(),c2.end()),c3 = str.substr(len/2+1,c1.size()); //c3== last string ,c1 = first string ,c2 = reversed of c1;
              //cout<<c1<<" "<<c2<<" "<<c3<<endl;
              if(c3>c2 || c3==c2){
                  a = str[len/2]-'0';
                  a++, a%=10;
                  res = c1;
                  res.push_back(a+'0');
                  res+=c2;
                }
              else res = c1,res.push_back(str[len/2]), res = res+c2;
              if(res[len/2]=='0' && (c3>c2 || c3==c2)){
                 s1 = len/2-1, s2 = s1+2;
                  while(1){
                    a = res[s1]-'0';
                    a++;
                    a%=10;
                    res[s1] = a+'0',res[s2] = a+'0';
                    if(a!=0) break;
                    s1--,s2++;
                    if(s1<0) {
                        printf("1");
                        res[res.size()-1] = '1';
                        break;
                      }
                  }
                }
             printf("%s\n",res.c_str());
         }//if len odd
        else {
  //if len even starts
          int s1,s2,a,b;
          c1 = str.substr(0,(len-2)/2),c2 = c1 , reverse(c2.begin(),c2.end());
          c3 = str.substr(len/2+1,c1.size());
         // cout<<c1<<" "<<c2<<" "<<c3<<endl;
          a = str[len/2-1]-'0',b = str[len/2]-'0';
          res =c1;
          if(c3>c1 || c3==c1){
              if(a>b) res.push_back(a+'0'),res.push_back(a+'0');
              else a++,a%=10,res.push_back(a+'0'),res.push_back(a+'0');
            }
          else {
              if(a>b) res.push_back(a+'0'),res.push_back(a+'0');
              else if(b>a) a++,a%=10, res.push_back(a+'0'),res.push_back(a+'0');
              else res.push_back(a+'0'),res.push_back(a+'0');
           }
          res+=c2;

if((c3>c1 || c3==c1) && res[len/2-1]=='0') {
    s1 = len/2-2, s2 = len/2+1;
    while(1){
        a = res[s1]-'0';
        a++;
        a%=10;
        res[s1] = a+'0',res[s2] = res[s1];
        if(a!=0) break;
        s1--,s2++;
        if(s1<0){
          printf("1");
            res[res.size()-1] = '1';
            break;
          }
      }
}
printf("%s\n",res.c_str());
     //if len even ends here
        }//if len even
        res.clear(),c1.clear(),c2.clear(),c3.clear();
    }//input
}