The problem: http://www.spoj.com/problems/PALIN/6
My code: http://ideone.com/YZN1oO3

I thought my code is perfect good even with the input having 1,000,000 digits, since it just deals with str.
I also use the random.randrange() to make some random numbers to test it, and don't have any trouble.

Is there anyone who can help me to find out what the problem is it?
Thanks!

def addone(s):
    if len(s) == 1: return str(int(s) + 1)
    elif s[-1] == '9': return addone(s[:-1]) + '0'
    return s[:-1] + str(int(s[-1]) + 1)

def get_palin(raw):
    half = len(raw) // 2
    if len(raw) == 1:
        if raw != '9': return str(int(raw) + 1)
        else: return '11'
    elif raw[:half] == raw[-half:][::-1]:
        return get_palin(addone(raw))
    
    for i in range(half - 1, -1, -1):
        if int(raw[i]) > int(raw[-i - 1]):
            return raw[:half] + raw[half:-half] + raw[:half][::-1]
        elif int(raw[i]) < int(raw[-i - 1]):
            new = addone(str(raw[:half + len(raw) % 2]))
            return new + new[:half][::-1]

result = []            
for test in range(int(input())):
    result.append(get_palin(input()))
print(*result, sep='\n', end='')