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

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

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

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);
        }
     }
}