#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
void printArray(vector<int> a){
cout<<"printing the array - ";
for(int i : a)
cout<<i<<" ";
cout<<endl;
}
string biggerPalin(string x)
{
int n = x.size();
int idx, i;
if (n & 1)
{
if (x[n / 2] != '9')
{
int a = (x[n / 2] - '0') + 1;
// cout<<a<<endl;
x.replace(n/2, 1, to_string(a));
// cout<<x[n/2]<<endl;
// cout<<x<<endl;
}
else
{
// x[n / 2] = '0';
x.replace(n/2, 1, to_string(0));
idx = n / 2;
i = 1;
while (x[idx - i] == '9' && idx - i >= 0)
{
// x[idx - i] = '0';
x.replace(idx-i, 1, to_string(0));
// x[idx + i] = '0';
x.replace(idx+i, 1, to_string(0));
i++;
}
if (x[0] == '0')
{
// x[n - 1] = '1';
x.replace(n-1, 1, to_string(1));
x = '1' + x;
}
else{
x.replace(idx-i, 1, to_string((x[idx-i]-'0') + 1));
// x[idx-i] = (x[idx-i] - '0') + 1;
// x[idx+i] = (x[idx+i] - '0') + 1;
x.replace(idx+i, 1, to_string((x[idx+i]-'0') + 1));
}
}
}
else
{
if (x[(n - 1) / 2] != '9')
{
// x[(n - 1) / 2] = (x[(n - 1) / 2] - '0') + 1;
x.replace((n-1)/2, 1, to_string((x[(n - 1) / 2] - '0') + 1));
// x[n / 2] = (x[n / 2] - '0') + 1;
x.replace(n/2, 1, to_string((x[n / 2] - '0') + 1));
}
else
{
idx = (n - 1) / 2;
i = 0;
while (x[idx - i] == '9' && idx - i >= 0)
{
// x[idx - i] = '0';
x.replace(idx-i, 1, to_string(0));
i++;
x.replace(idx+i, 1, to_string(0));
// x[idx + i] = '0';
}
if (x[0] == '0')
{
// x[n - 1] = '1';
x.replace(n-1, 1, to_string(1));
x = '1' + x;
}
else{
// x[idx-i] = (x[idx - i] - '0') + 1;
x.replace(idx-i, 1, to_string((x[idx - i] - '0') + 1));
i++;
x.replace(idx+i, 1, to_string((x[idx + i] - '0') + 1));
// x[idx + i] = (x[idx + i] - '0') + 1;
}
}
}
return x;
}
string findPalin(string str)
{
string res = str;
int n = str.size() - 1;
for (int i = 0; i < (n + 1) / 2; i++)
{
str[n - i] = str[i];
}
// cout<<res<<" "<<str<<endl;
if (str > res)
return str;
else
{
return biggerPalin(str);
}
}
int main()
{
int t;
cin >> t;
while (t > 0)
{
string str;
cin >> str;
// long long int num = findPalin(str);
cout << findPalin(str) << endl;
t--;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNzdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIHByaW50QXJyYXkodmVjdG9yPGludD4gYSl7Cgljb3V0PDwicHJpbnRpbmcgdGhlIGFycmF5IC0gIjsKCWZvcihpbnQgaSA6IGEpCgkJY291dDw8aTw8IiAiOwoKCWNvdXQ8PGVuZGw7Cn0KCgpzdHJpbmcgYmlnZ2VyUGFsaW4oc3RyaW5nIHgpCnsKICAgIGludCBuID0geC5zaXplKCk7CiAgICBpbnQgaWR4LCBpOwogICAgaWYgKG4gJiAxKQogICAgewogICAgICAgIGlmICh4W24gLyAyXSAhPSAnOScpCiAgICAgICAgewogICAgICAgIAlpbnQgYSA9ICh4W24gLyAyXSAtICcwJykgKyAxOwogICAgICAgIAkvLyBjb3V0PDxhPDxlbmRsOwogICAgICAgICAgICB4LnJlcGxhY2Uobi8yLCAxLCB0b19zdHJpbmcoYSkpOwogICAgICAgICAgICAvLyBjb3V0PDx4W24vMl08PGVuZGw7CiAgICAgICAgICAgIC8vIGNvdXQ8PHg8PGVuZGw7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIC8vIHhbbiAvIDJdID0gJzAnOwogICAgICAgICAgICB4LnJlcGxhY2Uobi8yLCAxLCB0b19zdHJpbmcoMCkpOwogICAgICAgICAgICBpZHggPSBuIC8gMjsKICAgICAgICAgICAgaSA9IDE7CiAgICAgICAgICAgIHdoaWxlICh4W2lkeCAtIGldID09ICc5JyAmJiBpZHggLSBpID49IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vIHhbaWR4IC0gaV0gPSAnMCc7CiAgICAgICAgICAgICAgICB4LnJlcGxhY2UoaWR4LWksIDEsIHRvX3N0cmluZygwKSk7CiAgICAgICAgICAgICAgICAvLyB4W2lkeCArIGldID0gJzAnOwogICAgICAgICAgICAgICAgeC5yZXBsYWNlKGlkeCtpLCAxLCB0b19zdHJpbmcoMCkpOwogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmICh4WzBdID09ICcwJykKICAgIAkJewogICAgICAgIAkJLy8geFtuIC0gMV0gPSAnMSc7CiAgICAgICAgCQl4LnJlcGxhY2Uobi0xLCAxLCB0b19zdHJpbmcoMSkpOwogICAgICAgIAkJeCA9ICcxJyArIHg7CiAgICAJCX0KICAgIAkJZWxzZXsKICAgIAkJCXgucmVwbGFjZShpZHgtaSwgMSwgdG9fc3RyaW5nKCh4W2lkeC1pXS0nMCcpICsgMSkpOwogICAgCQkJLy8geFtpZHgtaV0gPSAoeFtpZHgtaV0gLSAnMCcpICsgMTsKICAgIAkJCS8vIHhbaWR4K2ldID0gKHhbaWR4K2ldIC0gJzAnKSArIDE7CiAgICAJCQl4LnJlcGxhY2UoaWR4K2ksIDEsIHRvX3N0cmluZygoeFtpZHgraV0tJzAnKSArIDEpKTsKICAgIAkJfQogICAgICAgIH0KICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBpZiAoeFsobiAtIDEpIC8gMl0gIT0gJzknKQogICAgICAgIHsKICAgICAgICAgICAgLy8geFsobiAtIDEpIC8gMl0gPSAoeFsobiAtIDEpIC8gMl0gLSAnMCcpICsgMTsKICAgICAgICAgICAgeC5yZXBsYWNlKChuLTEpLzIsIDEsIHRvX3N0cmluZygoeFsobiAtIDEpIC8gMl0gLSAnMCcpICsgMSkpOwogICAgICAgICAgICAvLyB4W24gLyAyXSA9ICh4W24gLyAyXSAtICcwJykgKyAxOwogICAgICAgICAgICB4LnJlcGxhY2Uobi8yLCAxLCB0b19zdHJpbmcoKHhbbiAvIDJdIC0gJzAnKSArIDEpKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaWR4ID0gKG4gLSAxKSAvIDI7CiAgICAgICAgICAgIGkgPSAwOwogICAgICAgICAgICB3aGlsZSAoeFtpZHggLSBpXSA9PSAnOScgJiYgaWR4IC0gaSA+PSAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvLyB4W2lkeCAtIGldID0gJzAnOwogICAgICAgICAgICAgICAgeC5yZXBsYWNlKGlkeC1pLCAxLCB0b19zdHJpbmcoMCkpOwogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgICAgeC5yZXBsYWNlKGlkeCtpLCAxLCB0b19zdHJpbmcoMCkpOwogICAgICAgICAgICAgICAgLy8geFtpZHggKyBpXSA9ICcwJzsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoeFswXSA9PSAnMCcpCiAgICAJCXsKICAgICAgICAJCS8vIHhbbiAtIDFdID0gJzEnOwogICAgICAgIAkJeC5yZXBsYWNlKG4tMSwgMSwgdG9fc3RyaW5nKDEpKTsKICAgICAgICAJCXggPSAnMScgKyB4OwogICAgCQl9CiAgICAJCWVsc2V7CiAgICAJCQkvLyB4W2lkeC1pXSA9ICh4W2lkeCAtIGldIC0gJzAnKSArIDE7CiAgICAJCQl4LnJlcGxhY2UoaWR4LWksIDEsIHRvX3N0cmluZygoeFtpZHggLSBpXSAtICcwJykgKyAxKSk7CiAgICAJCQlpKys7CiAgICAJCQl4LnJlcGxhY2UoaWR4K2ksIDEsIHRvX3N0cmluZygoeFtpZHggKyBpXSAtICcwJykgKyAxKSk7CiAgICAJCQkvLyB4W2lkeCArIGldID0gKHhbaWR4ICsgaV0gLSAnMCcpICsgMTsKICAgIAkJfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiB4Owp9CgpzdHJpbmcgZmluZFBhbGluKHN0cmluZyBzdHIpCnsKICAgIHN0cmluZyByZXMgPSBzdHI7CiAgICBpbnQgbiA9IHN0ci5zaXplKCkgLSAxOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAobiArIDEpIC8gMjsgaSsrKQogICAgewogICAgICAgIHN0cltuIC0gaV0gPSBzdHJbaV07CiAgICB9CgkvLyBjb3V0PDxyZXM8PCIgIjw8c3RyPDxlbmRsOwogICAgaWYgKHN0ciA+IHJlcykKICAgICAgICByZXR1cm4gc3RyOwogICAgZWxzZQogICAgewogICAgICAgIHJldHVybiBiaWdnZXJQYWxpbihzdHIpOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSAodCA+IDApCiAgICB7CiAgICAgICAgc3RyaW5nIHN0cjsKICAgICAgICBjaW4gPj4gc3RyOwogICAgICAgIC8vIGxvbmcgbG9uZyBpbnQgbnVtID0gZmluZFBhbGluKHN0cik7CiAgICAgICAgY291dCA8PCBmaW5kUGFsaW4oc3RyKSA8PCBlbmRsOwogICAgICAgIHQtLTsKICAgIH0KfQ==