#include <cstdio>
#include <cstring>

int t = 0;
char buf[1000002];
unsigned int middleL = 0;
unsigned int middleR = 0;

void shr()
{

}
void computeNextPalindrome()
{
    unsigned int bufLength = strlen(buf);
    bool bufLenEven = (bufLength % 2 == 0);
    middleR = bufLength / 2;
    if(bufLenEven)
    {
        middleL = bufLength / 2 - 1;
    }
    else
    {
        middleL = bufLength / 2;
    }
    unsigned int i = 0;
    while((middleR + i < bufLength) && (buf[middleL-i] == buf[middleR+i]))
    {
        i++;
    }
    if(buf[middleL - i] < buf[middleR + i])
    {
        if(bufLenEven)
        {
            buf[middleL]++;
            buf[middleR] = buf[middleL];
        }
        else
        {
            buf[middleR]++;

        }
    }
    else
    {
        buf[middleR] = buf[middleL];
    }
    for(; middleR + i < bufLength; i++)
    {
        buf[middleR + i] = buf[middleL - i];
    }

}

int main()
{
	scanf("%d", &t);

	for(unsigned short int i = 0; i < t; i++)
	{
		scanf("%s", buf);
        computeNextPalindrome();
        printf("%s\n", buf);
	}
	return 0;

}