【題意簡述】
輸入一個正整數k，輸出大于k的最小回文整數。
【分析】
由于題目給的數字超級大(1000000位)，所以暴力模擬顯然會嚴重超時，于是考慮從數的特點來求解。

首先假設一個n位10進制數字可以表示為 A[0]A[1]A[2]...A[N-1]，那么
1.我們希望從中間開始修改數字，使數增加的盡量少。
如:133151330，顯然我們不會去改變它使之成為133252331，因為他顯然比133161331來的大。
2.如果給你的數已經是一個Palindrome數，那你顯然應該從最中間的開始改起。
如:808，顯然你不會把它改成909而是把它改為818。
3.如果存在前半部分的某個數A[i]小于后半部分對應的數A[N-1-i]，那么我們必須把前半部分的那個數變成后半部分的數才能滿足Palindrome的條件，可是顯然這增加過多，所以我們希望在它后面的某些數A[j]拿去增加 ，這樣數字變大了，而且我們不需要使A[i]變大(顯然A[i]在A[j]前面幾位,增加A[j]的話，數字增加的更少)。
4.如果某數全為9，那么顯然它的下一個Palindrome必然為10...01,其中有(N-1)個0。

于是得到下列算法:
a.首先判斷串中是否全為9，如果是則輸出10..01(0有N-1個),否則轉下一步。
b.用2個指針i,j指向前、后半部分，顯然i從前半部分的最右邊，j從后半部分的最左邊開始掃描。自然這里還需要考慮到N的奇偶性，即:i=(len>>1)-1,j=i+1+(len&0x1);
c.記錄對應位置的數字的大小情況，并把前半部分的內容copy到后半部分對應的位上。
d.如果存在前半部分的某些數小于后半部分的某些數，或該數本身為Palindrome數，那么進行進位操作，即從最中間開始+1.一直加到沒有進位。

import java.util.*;
import java.io.*;

public class SPOJ_5{
    
    public static void main(String rgs[]) throws Exception
    {
        BufferedReader stdin = 
            new BufferedReader(
                new InputStreamReader(System.in));        
        String s = stdin.readLine();  
        int m,t = Integer.parseInt(s);
        int[] dp=new int[1000002];
        for(m=0;m<t;m++){
            s = stdin.readLine();                    
            StringBuilder str=new StringBuilder(s);
            
            int len=str.length(),i,j;
            boolean alln=true;
            for(i=0;i<len && alln;i++){
                if(str.charAt(i)!='9')
                    alln=false;
            }
            if(alln){
                System.out.print("1");
                for(i=0;i<len-1;i++)
                    System.out.print("0");
                System.out.println("1");
                continue;
            }
            
            boolean flag=true;;
            i=(len>>1)-1;
            j=(len>>1)+(len&0x1);
            Arrays.fill(dp,0);
            while(j<len){
                if(str.charAt(i)>str.charAt(j))
                    dp[j]=-1;
                else if(str.charAt(i)<str.charAt(j))
                    dp[j]=1;
                i--;
                j++;
            }
            i=(len>>1)+(len&0x1);
            while(i<len){
                if(dp[i]==-1)
                    break;
                if(dp[i]==1){
                    flag=false;
                    break;
                }
                i++;
            }
            if(i==len)
                flag=false;
            for(i=(len>>1)+(len&0x1);i<len;++i){
                if(dp[i]!=0)
                    str.setCharAt(i,str.charAt(len-1-i));
            }
            
            if(!flag){                
                i=(len>>1);
                if(len%2==0)
                    i--;
                int buf=1;
                while((buf==1) && (i>=0)){
                    buf=(str.charAt(i)+1-'0')/10;
                    int p=(int)(str.charAt(i)-'0'+1)%10;
                    char c=(char)(p+48);
                    str.setCharAt(i,c);
                    str.setCharAt(len-1-i,c);
                    i--;
                }
            }
            
            System.out.println(str);
        }
     }
}