1. #include <cstdio>
2. #include <cstring>
3.  
4. int t = 0;
5. char buf[1000002];
6. unsigned int middleL = 0;
7. unsigned int middleR = 0;
8.  
9. void shr()
10. {
11.  
12. }
13. void computeNextPalindrome()
14. {
15.     unsigned int bufLength = strlen(buf);
16.     bool bufLenEven = (bufLength % 2 == 0);
17.     middleR = bufLength / 2;
18.     if(bufLenEven)
19.     {
20.         middleL = bufLength / 2 - 1;
21.     }
22.     else
23.     {
24.         middleL = bufLength / 2;
25.     }
26.     unsigned int i = 0;
27.     while((middleR + i < bufLength) && (buf[middleL-i] == buf[middleR+i]))
28.     {
29.         i++;
30.     }
31.     if(buf[middleL - i] < buf[middleR + i])
32.     {
33.         if(bufLenEven)
34.         {
35.             buf[middleL]++;
36.             buf[middleR] = buf[middleL];
37.         }
38.         else
39.         {
40.             buf[middleR]++;
41.  
42.         }
43.     }
44.     else
45.     {
46.         buf[middleR] = buf[middleL];
47.     }
48.     for(; middleR + i < bufLength; i++)
49.     {
50.         buf[middleR + i] = buf[middleL - i];
51.     }
52.  
53. }
54.  
55. int main()
56. {
57.         scanf("%d", &t);
58.  
59.         for(unsigned short int i = 0; i < t; i++)
60.         {
61.                 scanf("%s", buf);
62.         computeNextPalindrome();
63.         printf("%s\n", buf);
64.         }
65.         return 0;
66.  
67. }
68.