the next palindrome in Java

Question

i have some problems on SPOJ with the task. i always get "time limit exceed". Please help me to improve the efficiency of my code. I'm a beginner.

THE TASK: A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input: 2 808 2133

Output: 818 2222

Warning: large Input/Output data, be careful with certain languages

MY SOLUTION:

    import java.util.*;
import java.lang.*;
import java.math.BigInteger;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            for(int i=0; i<n; ++i){
                System.out.println(findpalindrome(sc.next()));
            }
    }

    private static String findpalindrome(String n){
        if(n.length()==1){
            if(n.charAt(0)-'0'<9)return ""+(n.charAt(0)-'0'+1);
            else return "11";
        }
        String result="";
            if(firstpartlarger(n)){
                if(n.length()%2==0)result=n.substring(0, n.length()/2)+reverse(n.substring(0, n.length()/2));
                else result=n.substring(0, n.length()/2)+n.charAt(n.length()/2)+reverse(n.substring(0, n.length()/2));
            }
            else{
                if(n.length()%2==0){
                result=increase(n.substring(0, n.length()/2));
                result+=reverse(result.substring(0, result.length()-1));
                }
                else{
                result=increase(n.substring(0, n.length()/2+1));
                result+=reverse(result.substring(0, n.length()/2));
                }
            }
            return result;
        }


        private static String increase(String n){
            BigInteger i=new BigInteger(n);
            i=i.add(BigInteger.ONE);
            return i.toString();
        }


    private static String reverse(String n){
        StringBuilder builder=new StringBuilder(n);
        builder.reverse();
        return builder+"";
    }

    private static boolean firstpartlarger(String n){
        return reverse(n.substring(0,  n.length()/2)).compareTo(n.substring(n.length()-n.length()/2))>0;
    }

}