gistfile1.py

def read_input():
    import sys

    data = []

    n = int(input())
    for i in range(n):
        data.append(input())

    return data

def add_one(s):
    """Adds 1 to s where s.isdigit() is true.

    >>> add_one("0")
    '1'
    >>> add_one("11")
    '12'
    >>> add_one("19")
    '20'
    >>> add_one("99")
    '100'
    >>> add_one("909")
    '910'
    """

    i = len(s) - 1
    while (s[i] == "9"):
        s = s[:i] + "0" + s[i+1:]
        i = i - 1

    if (i == -1):
        s = "1" + s
    else:
        s = s[:i] + str(int(s[i]) + 1) + s[i+1:]

    return s

def is_palindrome(s):
    """Returns true if s is a palindrome, false otherwise.

    >>> is_palindrome("")
    True
    >>> is_palindrome("x")
    True
    >>> is_palindrome("xx")
    True
    >>> is_palindrome("xy")
    False
    >>> is_palindrome("xyx")
    True
    >>> is_palindrome("xyyx")
    True
    """

    if (s == s[::-1]):
        return True
    else:
        return False

def make_palindrome(num):
    """Returns the next highest palindrome of num where num.isdigit() is true.

    >>> make_palindrome("0")
    '1'
    >>> make_palindrome("11")
    '22'
    >>> make_palindrome("12")
    '22'
    >>> make_palindrome("120")
    '121'
    >>> make_palindrome("101")
    '111'
    >>> make_palindrome("999")
    '10001'
    >>> make_palindrome("1234")
    '1331'
    """

    import math

    if len(num) == 1: return str(int(num) + 1)

    mid = math.ceil(len(num) / 2)

    if len(num) % 2 == 0:
        a = num[:mid]
        br = num[mid:][::-1]

        if (br >= a):
            a = add_one(a)
            ar = a[::-1]
        else:
            ar = num[:mid][::-1]

        return a + ar
    else:
        a = num[:mid - 1]
        ar = num[:mid - 1][::-1]
        b = num[mid:]

        if (b < ar): return a + num[mid-1] + ar

        if (num[mid] < "9"): return a + add_one(num[mid-1]) + ar

        a = str(int(a) + 1)
        ar = a[::-1]

        return a + "0" + ar

if __name__ == "__main__":
    nums = read_input()

    for num in nums:
        print(make_palindrome(num))