from math import gcd
from itertools import count

# Solves the linear conguence ax ≡ b (mod n).
# The solution is returned as a tuple (c, m),
# meaning that ax ≡ b (mod n) if and only if x ≡ c (mod m).
# Returns None if no solution exists.
def solve_congruence(a, b, n):
    d = gcd(a, n)
    if(b % d != 0): return None
    a, b, n = a//d, b//d, n//d
    return (b*pow(a, -1, n) % n, n)

# Returns the smallest d-digit palindrome in base b
# congruent to a (modulo n), or None if no such palindrome exists.
def least_d_digit_palindrome(d, a, n, b=10, allow_leading_zeros=False):
    a %= n
    if(d == 0): return 0 if a == 0 else None
    if(d == 1): return next((i for i in range(1 - allow_leading_zeros, b) if i % n == a), None)
    for i in range(1 - allow_leading_zeros, b):
        t = solve_congruence(b, a - i - i*b**(d-1), n)
        if t is not None:
            x = least_d_digit_palindrome(d-2, t[0], t[1], b, True)
            if x is not None: return i*b**(d-1) + x*b + i
    return None

# Returns the smallest positive palindrome in base b
# congruent to a (modulo n), or 0 if no such palindrome exists.
def least_palindrome(a, n, b=10):
    if(a % b == n % b == 0): return 0
    for d in count(1):
        result = least_d_digit_palindrome(d, a, n, b)
        if result is not None: return result

print("0 0")
for n in range(1, 8181):
    print(n, least_palindrome(0, n))