#include<stdio.h>
#include<string.h>
char a[1000000];
void even(int length);
void odd(int length);
void strrev(char *a, char *b, int length);
int check_higher(char *a, char *b, int length);
int main(){
int t,i;
int length;
while(t--){
if(length==1)
else{
if(length%2==0)
even(length);
else
odd(length);
}
}
return 0;
}
void odd(int length){
int i,j,check,temp;
char left[5000],right[5000];
for(i=0;i<length/2;i++)
left[i]=a[i];
for(i=length/2+1,j=0;i<length;i++,j++)
right[j]=a[i];
//printf("%s %s\n",left,right);
char leftRev[5000];
strrev(left,leftRev,length/2);
check=check_higher(leftRev,right,length/2);
if(check==1){
printf("%s%c%s",left
,a
[length
/2],right
); }
else{
temp=length/2-1;
if(a[length/2]=='9'){
while(left[temp]=='9' && temp>=0){
left[temp]='0';
temp--;
}
if(temp>=0)
left[temp]++;
else{
for(i=1;i<length;i++)
}
}
else{
printf("%s%c%s",left
,++a
[length
/2],leftRev
); }
}
return;
}
void even(int length){
int i,j,check,temp;
char left[5000],right[5000];
for(i=0;i<length/2;i++)
left[i]=a[i];
for(i=length/2,j=0;i<length;i++,j++)
right[j]=a[i];
//printf("%s %s\n",left,right);
char leftRev[5000];
strrev(left,leftRev,length/2);//Reverse Left half
//printf("%s\n",leftRev);
check=check_higher(leftRev,right,length/2);//Checks if the left half is higher or the right half
if(check==1){
}
else{
temp=length/2-1;
//printf("%d\n",temp);
while(left[temp]=='9' && temp>=0){
left[temp]='0';
temp--;
}
if(temp>=0)
left[temp]++;
else{
left[0]='1';
for(i=1;i<=length/2;i++)
left[i]='0';
}
//left[length/2-1]++;
strrev(left,leftRev,length/2);
}
return;
}
void strrev(char *a, char *b, int length){
int i,j;
for(i=0,j=length-1;i<length;i++,j--)
b[j]=a[i];
return;
}
int check_higher(char *a, char *b, int length){
int i=0;
while(a[i] == b[i] && i<length){
i++;
}
if(i==length-1)
return 2;
else if(a[i]-'0' > b[i]-'0')
return 1;
else
return 2;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CmNoYXIgYVsxMDAwMDAwXTsKdm9pZCBldmVuKGludCBsZW5ndGgpOwp2b2lkIG9kZChpbnQgbGVuZ3RoKTsKdm9pZCBzdHJyZXYoY2hhciAqYSwgY2hhciAqYiwgaW50IGxlbmd0aCk7CmludCBjaGVja19oaWdoZXIoY2hhciAqYSwgY2hhciAqYiwgaW50IGxlbmd0aCk7CmludCBtYWluKCl7CglpbnQgdCxpOwoJaW50IGxlbmd0aDsKCXNjYW5mKCIlZFxuIiwmdCk7Cgl3aGlsZSh0LS0pewoJZ2V0cyhhKTsKCWxlbmd0aD1zdHJsZW4oYSk7CglpZihsZW5ndGg9PTEpCglwcmludGYoIiVjXG4iLCsrYVswXSk7CgllbHNlewoJCWlmKGxlbmd0aCUyPT0wKQoJCQlldmVuKGxlbmd0aCk7CgkJZWxzZQoJCQlvZGQobGVuZ3RoKTsKCQlwcmludGYoIlxuIik7Cgl9Cgl9CglyZXR1cm4gMDsKfQoKdm9pZCBvZGQoaW50IGxlbmd0aCl7CglpbnQgaSxqLGNoZWNrLHRlbXA7CgljaGFyIGxlZnRbNTAwMF0scmlnaHRbNTAwMF07Cglmb3IoaT0wO2k8bGVuZ3RoLzI7aSsrKQoJCWxlZnRbaV09YVtpXTsKCWZvcihpPWxlbmd0aC8yKzEsaj0wO2k8bGVuZ3RoO2krKyxqKyspCgkJcmlnaHRbal09YVtpXTsKCS8vcHJpbnRmKCIlcyAlc1xuIixsZWZ0LHJpZ2h0KTsKCWNoYXIgbGVmdFJldls1MDAwXTsKCXN0cnJldihsZWZ0LGxlZnRSZXYsbGVuZ3RoLzIpOwoJY2hlY2s9Y2hlY2tfaGlnaGVyKGxlZnRSZXYscmlnaHQsbGVuZ3RoLzIpOwoJaWYoY2hlY2s9PTEpewoJCXByaW50ZigiJXMlYyVzIixsZWZ0LGFbbGVuZ3RoLzJdLHJpZ2h0KTsKCX0KCWVsc2V7CgkJdGVtcD1sZW5ndGgvMi0xOwoJCWlmKGFbbGVuZ3RoLzJdPT0nOScpewoJCQl3aGlsZShsZWZ0W3RlbXBdPT0nOScgJiYgdGVtcD49MCl7CgkJCQlsZWZ0W3RlbXBdPScwJzsKCQkJCXRlbXAtLTsKCQkJfQoJCQlpZih0ZW1wPj0wKQoJCQkJbGVmdFt0ZW1wXSsrOwkJCgkJCWVsc2V7CgkJCQlwcmludGYoIjEiKTsKCQkJCWZvcihpPTE7aTxsZW5ndGg7aSsrKQoJCQkJCXByaW50ZigiMCIpOwoJCQkJcHJpbnRmKCIxIik7CgkJCX0JCgkJfQoJCWVsc2V7CgkJCXByaW50ZigiJXMlYyVzIixsZWZ0LCsrYVtsZW5ndGgvMl0sbGVmdFJldik7CgkJfQoJfQkKCXJldHVybjsKfQoKdm9pZCBldmVuKGludCBsZW5ndGgpewoJaW50IGksaixjaGVjayx0ZW1wOwoJY2hhciBsZWZ0WzUwMDBdLHJpZ2h0WzUwMDBdOwoJZm9yKGk9MDtpPGxlbmd0aC8yO2krKykKCQlsZWZ0W2ldPWFbaV07Cglmb3IoaT1sZW5ndGgvMixqPTA7aTxsZW5ndGg7aSsrLGorKykKCQlyaWdodFtqXT1hW2ldOwoJLy9wcmludGYoIiVzICVzXG4iLGxlZnQscmlnaHQpOwoJY2hhciBsZWZ0UmV2WzUwMDBdOwoJc3RycmV2KGxlZnQsbGVmdFJldixsZW5ndGgvMik7Ly9SZXZlcnNlIExlZnQgaGFsZgoJLy9wcmludGYoIiVzXG4iLGxlZnRSZXYpOwoJY2hlY2s9Y2hlY2tfaGlnaGVyKGxlZnRSZXYscmlnaHQsbGVuZ3RoLzIpOy8vQ2hlY2tzIGlmIHRoZSBsZWZ0IGhhbGYgaXMgaGlnaGVyIG9yIHRoZSByaWdodCBoYWxmCglpZihjaGVjaz09MSl7CgkJc3RyY3B5KHJpZ2h0LGxlZnRSZXYpOwoJCXByaW50ZigiJXMlcyIsbGVmdCxyaWdodCk7Cgl9CgllbHNlewoJCXRlbXA9bGVuZ3RoLzItMTsKCQkvL3ByaW50ZigiJWRcbiIsdGVtcCk7CgkJd2hpbGUobGVmdFt0ZW1wXT09JzknICYmIHRlbXA+PTApewoJCQlsZWZ0W3RlbXBdPScwJzsKCQkJdGVtcC0tOwoJCX0KCQlpZih0ZW1wPj0wKQoJCQlsZWZ0W3RlbXBdKys7CgkJZWxzZXsKCQkJbGVmdFswXT0nMSc7CgkJCWZvcihpPTE7aTw9bGVuZ3RoLzI7aSsrKQoJCQkJbGVmdFtpXT0nMCc7CgkJfQoJCS8vbGVmdFtsZW5ndGgvMi0xXSsrOwoJCXN0cnJldihsZWZ0LGxlZnRSZXYsbGVuZ3RoLzIpOwoJCXN0cmNweShyaWdodCxsZWZ0UmV2KTsKCQlwcmludGYoIiVzJXMiLGxlZnQscmlnaHQpOwoJfQoJcmV0dXJuOwp9Cgp2b2lkIHN0cnJldihjaGFyICphLCBjaGFyICpiLCBpbnQgbGVuZ3RoKXsKCWludCBpLGo7Cglmb3IoaT0wLGo9bGVuZ3RoLTE7aTxsZW5ndGg7aSsrLGotLSkKCQliW2pdPWFbaV07CglyZXR1cm47Cgp9CgppbnQgY2hlY2tfaGlnaGVyKGNoYXIgKmEsIGNoYXIgKmIsIGludCBsZW5ndGgpewoJaW50IGk9MDsKCXdoaWxlKGFbaV0gPT0gYltpXSAmJiBpPGxlbmd0aCl7CgkJaSsrOwoJfQoJaWYoaT09bGVuZ3RoLTEpCgkJcmV0dXJuIDI7CgllbHNlIGlmKGFbaV0tJzAnID4gYltpXS0nMCcpCgkJcmV0dXJuIDE7CgllbHNlCgkJcmV0dXJuIDI7Cn0=