#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
 
char *strrev(char *str){
	char *p1, *p2;
	if(!str || !*str)
		return str;
	for( p1 = str, p2 = strlen(str)+str-1; p1<p2; ++p1, --p2){
		*p1 ^= *p2;
		*p2 ^= *p1;
		*p1 ^= *p2;
	}
	return str;
}
 
void append(char *s, char c){
	int len = strlen(s);
	s[len] = c;
	s[len + 1] = '\0';
}
 
char *removeLeadingZeros(char *s){
	char *tmp;
	for(int i=0; i<strlen(s); i++){
		if(s[i] != '0'){
			tmp = s+i;
			break;
		}
	}
	return tmp;
}
 
void palin(char *s){
	//printf("s: %s\n", s);
	int midpoint = floor(strlen(s)/2);
	char p[midpoint];
	char q[midpoint];
	int odd = strlen(s) % 2;
	strncpy(p, s, midpoint);
	p[midpoint] = '\0';
	strcpy(q, s+midpoint+odd);
	//printf("p: %s\tq: %s\n", p, q);
	int i=midpoint-1, j=0;
	do{
		int a, b;
		a = p[i];
		b = q[j];
		if(a == b){
			i--;
			j++;
			continue;
		}
		if(a < b){
			if(odd)
				s[midpoint] += 1;
			else
				p[midpoint-1] += 1;
		}
		break;
	}while(1);
	char rev[strlen(p)];
	strcpy(rev, p);
	strrev(rev);
	//printf("p: %s\nrev: %s\n", p, rev);
	if(odd)
		append(p, s[midpoint]);
	//printf("p: %s\tq: %s\n", p, q);
	strcat(p, rev);
	printf("%s\n", p);
}
 
int main(){
	int t;
	scanf("%i", &t);
	while(t--){
		char s[1000000];
		scanf("%s", s);
		char *p;
		p = removeLeadingZeros(s);
		s[strlen(s) - 1] += 1;
		palin(p);
	}
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8bWF0aC5oPgoKY2hhciAqc3RycmV2KGNoYXIgKnN0cil7CgljaGFyICpwMSwgKnAyOwoJaWYoIXN0ciB8fCAhKnN0cikKCQlyZXR1cm4gc3RyOwoJZm9yKCBwMSA9IHN0ciwgcDIgPSBzdHJsZW4oc3RyKStzdHItMTsgcDE8cDI7ICsrcDEsIC0tcDIpewoJCSpwMSBePSAqcDI7CgkJKnAyIF49ICpwMTsKCQkqcDEgXj0gKnAyOwoJfQoJcmV0dXJuIHN0cjsKfQoKdm9pZCBhcHBlbmQoY2hhciAqcywgY2hhciBjKXsKCWludCBsZW4gPSBzdHJsZW4ocyk7CglzW2xlbl0gPSBjOwoJc1tsZW4gKyAxXSA9ICdcMCc7Cn0KCmNoYXIgKnJlbW92ZUxlYWRpbmdaZXJvcyhjaGFyICpzKXsKCWNoYXIgKnRtcDsKCWZvcihpbnQgaT0wOyBpPHN0cmxlbihzKTsgaSsrKXsKCQlpZihzW2ldICE9ICcwJyl7CgkJCXRtcCA9IHMraTsKCQkJYnJlYWs7CgkJfQoJfQoJcmV0dXJuIHRtcDsKfQoKdm9pZCBwYWxpbihjaGFyICpzKXsKCS8vcHJpbnRmKCJzOiAlc1xuIiwgcyk7CglpbnQgbWlkcG9pbnQgPSBmbG9vcihzdHJsZW4ocykvMik7CgljaGFyIHBbbWlkcG9pbnRdOwoJY2hhciBxW21pZHBvaW50XTsKCWludCBvZGQgPSBzdHJsZW4ocykgJSAyOwoJc3RybmNweShwLCBzLCBtaWRwb2ludCk7CglwW21pZHBvaW50XSA9ICdcMCc7CglzdHJjcHkocSwgcyttaWRwb2ludCtvZGQpOwoJLy9wcmludGYoInA6ICVzXHRxOiAlc1xuIiwgcCwgcSk7CglpbnQgaT1taWRwb2ludC0xLCBqPTA7Cglkb3sKCQlpbnQgYSwgYjsKCQlhID0gcFtpXTsKCQliID0gcVtqXTsKCQlpZihhID09IGIpewoJCQlpLS07CgkJCWorKzsKCQkJY29udGludWU7CgkJfQoJCWlmKGEgPCBiKXsKCQkJaWYob2RkKQoJCQkJc1ttaWRwb2ludF0gKz0gMTsKCQkJZWxzZQoJCQkJcFttaWRwb2ludC0xXSArPSAxOwoJCX0KCQlicmVhazsKCX13aGlsZSgxKTsKCWNoYXIgcmV2W3N0cmxlbihwKV07CglzdHJjcHkocmV2LCBwKTsKCXN0cnJldihyZXYpOwoJLy9wcmludGYoInA6ICVzXG5yZXY6ICVzXG4iLCBwLCByZXYpOwoJaWYob2RkKQoJCWFwcGVuZChwLCBzW21pZHBvaW50XSk7CgkvL3ByaW50ZigicDogJXNcdHE6ICVzXG4iLCBwLCBxKTsKCXN0cmNhdChwLCByZXYpOwoJcHJpbnRmKCIlc1xuIiwgcCk7Cn0KCmludCBtYWluKCl7CglpbnQgdDsKCXNjYW5mKCIlaSIsICZ0KTsKCXdoaWxlKHQtLSl7CgkJY2hhciBzWzEwMDAwMDBdOwoJCXNjYW5mKCIlcyIsIHMpOwoJCWNoYXIgKnA7CgkJcCA9IHJlbW92ZUxlYWRpbmdaZXJvcyhzKTsKCQlzW3N0cmxlbihzKSAtIDFdICs9IDE7CgkJcGFsaW4ocCk7Cgl9CglyZXR1cm4gMDsKfQ==

MTUKODA4CjIxMjIKOTIxMjM0NTk3NjgzNjE0NTQxNTY1MTY0NTEyNjQyMTU2NDE1NjQyMTU2NDIxCjAxMjM0NTg3OTY0NTMxMjU2NDk3ODU0CjUxNDE1NDcxNTI0Nwo2NTQxNjUyMQo2NDE1NjQ3NTEyCjYxNTY3NTE2NzIxCjMyNjQ1MTcKMTM0NTIxNjU3CjY1NDY0MTY1MTIKMjY1NDE4NwozMTQ1NzI2OAozMTU0Mjc1MTcKMjU0Nzg5NjY=

15
808
2122
921234597683614541565164512642156415642156421
01234587964531256497854
514154715247
65416521
6415647512
61567516721
3264517
134521657
6546416512
2654187
31457268
315427517
25478966