#include <stdio.h>
#include <math.h>
#include <string.h>
void solve(char c[]){
int ok = 0;
for(int i = 0; i < strlen(c); i++){
if(c[i] == '1') ok = 1;
else if(!(c[i] == '0' || c[i] == '8' || c[i] == '9')){
ok = 0;
break;
}
}
if(!ok){
printf("INVALID\n");
return ;
}
ok = 0;
for(int i = 0; i < strlen(c); i ++){
if(c[i] == '1'){
printf("1");
ok = 1;
}
else if(ok != 0){
printf("0");
}
}
printf("\n");
}
int main(){
int t;
scanf("%d", &t);
while(t--){
char c[20];
scanf("%s",c);
solve(c);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCnZvaWQgc29sdmUoY2hhciBjW10pewoJaW50IG9rID0gMDsKCWZvcihpbnQgaSA9IDA7IGkgPCBzdHJsZW4oYyk7IGkrKyl7CgkJaWYoY1tpXSA9PSAnMScpIG9rID0gMTsKCQllbHNlIGlmKCEoY1tpXSA9PSAnMCcgfHwgY1tpXSA9PSAnOCcgfHwgY1tpXSA9PSAnOScpKXsKCQkJb2sgPSAwOwoJCQlicmVhazsKCQl9Cgl9CglpZighb2spewoJCXByaW50ZigiSU5WQUxJRFxuIik7CgkJcmV0dXJuIDsKCX0KCW9rID0gMDsKCWZvcihpbnQgaSA9IDA7IGkgPCBzdHJsZW4oYyk7IGkgKyspewoJCWlmKGNbaV0gPT0gJzEnKXsKCQkJcHJpbnRmKCIxIik7CgkJCW9rID0gMTsKCQl9CgkJZWxzZSBpZihvayAhPSAwKXsKCQkJcHJpbnRmKCIwIik7CgkJfQoJfQoJcHJpbnRmKCJcbiIpOwkKfQoKaW50IG1haW4oKXsKCWludCB0OwoJc2NhbmYoIiVkIiwgJnQpOwoJd2hpbGUodC0tKXsKCQljaGFyIGNbMjBdOwoJCXNjYW5mKCIlcyIsYyk7CgkJc29sdmUoYyk7Cgl9Cn0=