#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <unistd.h>
char *nozeros(char *s){
int i;
if(s[i] != '0')
break;
}
return s+i;
}
int all9(char *s){
for(int i
=0; i
<strlen(s
); i
++){ if(s[i] != '9')
return 0;
}
return 1;
}
void incrementFromMiddle(char *s, int pos){
for(int i=pos; i>=0; i--){
if(s[i] != '9'){
s[i] += 1;
s[(len%2 == 0)?len-i-1:len-i] = s[i];
break;
}
s[i] = '0';
s[(len%2 == 0)?len-i-1:len-i] = s[i];
}
}
int main(){
int t;
while(t--){
char s[1000000];
char *ptr = nozeros(s);
if(all9(ptr)){
ptr[0] = '1';
ptr[len] = '1';
ptr[len + 1] = '\0';
continue;
}
for(int i=len-1; i>=0; i--){
if(ptr[i] != '9'){
ptr[i] += 1;
break;
}
ptr[i] = '0';
}
short firstTime=1;
short odd = len % 2;
int midpoint
= floor(len
/ 2); int start = (odd)? midpoint+1 : midpoint;
for(int i=start; i<len; i++){
if(ptr[i] == ptr[len - i - 1]){
continue;
}
if(ptr[i] > ptr[len - i - 1] && firstTime == 1){
if(odd)
incrementFromMiddle(ptr, midpoint);
else
incrementFromMiddle(ptr, midpoint-1);
}
ptr[i] = ptr[len - i - 1];
firstTime = 0;
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8dW5pc3RkLmg+CgpjaGFyICpub3plcm9zKGNoYXIgKnMpewoJaW50IGk7Cglmb3IoaT0wOyBpPHN0cmxlbihzKTsgaSsrKXsKCQlpZihzW2ldICE9ICcwJykKCQkJYnJlYWs7Cgl9CglyZXR1cm4gcytpOwp9CgppbnQgYWxsOShjaGFyICpzKXsKCWZvcihpbnQgaT0wOyBpPHN0cmxlbihzKTsgaSsrKXsKCQlpZihzW2ldICE9ICc5JykKCQkJcmV0dXJuIDA7Cgl9CglyZXR1cm4gMTsKfQoKdm9pZCBpbmNyZW1lbnRGcm9tTWlkZGxlKGNoYXIgKnMsIGludCBwb3MpewoJaW50IGxlbiA9IHN0cmxlbihzKTsKCWZvcihpbnQgaT1wb3M7IGk+PTA7IGktLSl7CgkJaWYoc1tpXSAhPSAnOScpewoJCQlzW2ldICs9IDE7CgkJCXNbKGxlbiUyID09IDApP2xlbi1pLTE6bGVuLWldID0gc1tpXTsKCQkJYnJlYWs7CgkJfQoJCXNbaV0gPSAnMCc7CgkJc1sobGVuJTIgPT0gMCk/bGVuLWktMTpsZW4taV0gPSBzW2ldOwoJfQp9CgppbnQgbWFpbigpewoJaW50IHQ7CglzY2FuZigiJWkiLCAmdCk7Cgl3aGlsZSh0LS0pewoJCWNoYXIgc1sxMDAwMDAwXTsKCQlzY2FuZigiJXMiLCBzKTsKCQljaGFyICpwdHIgPSBub3plcm9zKHMpOwoJCWludCBsZW4gPSBzdHJsZW4ocHRyKTsKCQlpZihhbGw5KHB0cikpewoJCQltZW1zZXQocHRyLCAnMCcsIGxlbik7CgkJCXB0clswXSA9ICcxJzsKCQkJcHRyW2xlbl0gPSAnMSc7CgkJCXB0cltsZW4gKyAxXSA9ICdcMCc7CgkJCXByaW50ZigiJXNcbiIsIHB0cik7CgkJCWNvbnRpbnVlOwoJCX0KCQlmb3IoaW50IGk9bGVuLTE7IGk+PTA7IGktLSl7CgkJCWlmKHB0cltpXSAhPSAnOScpewoJCQkJcHRyW2ldICs9IDE7CgkJCQlicmVhazsKCQkJfQoJCQlwdHJbaV0gPSAnMCc7CgkJfQoJCXNob3J0IGZpcnN0VGltZT0xOwoJCXNob3J0IG9kZCA9IGxlbiAlIDI7CgkJaW50IG1pZHBvaW50ID0gZmxvb3IobGVuIC8gMik7CgkJaW50IHN0YXJ0ID0gKG9kZCk/IG1pZHBvaW50KzEgOiBtaWRwb2ludDsKCQlmb3IoaW50IGk9c3RhcnQ7IGk8bGVuOyBpKyspewoJCQlpZihwdHJbaV0gPT0gcHRyW2xlbiAtIGkgLSAxXSl7CgkJCQljb250aW51ZTsKCQkJfQoJCQlpZihwdHJbaV0gPiBwdHJbbGVuIC0gaSAtIDFdICYmIGZpcnN0VGltZSA9PSAxKXsKCQkJCWlmKG9kZCkKCQkJCQlpbmNyZW1lbnRGcm9tTWlkZGxlKHB0ciwgbWlkcG9pbnQpOwoJCQkJZWxzZQoJCQkJCWluY3JlbWVudEZyb21NaWRkbGUocHRyLCBtaWRwb2ludC0xKTsKCQkJfQoJCQlwdHJbaV0gPSBwdHJbbGVuIC0gaSAtIDFdOwoJCQlmaXJzdFRpbWUgPSAwOwoJCX0KCQlwcmludGYoIiVzXG4iLCBwdHIpOwoJfQoJcmV0dXJuIDA7Cn0=