GCJ 2013 Qual C http://oeis.org/A057135

c.py

# coding: utf-8

import bisect

def palindromes():
    for d in xrange(7):
        for i in xrange(10 ** d, 10 ** (d + 1)):
            yield i * 10**d + long(str(i)[::-1]) % (10 ** d)
        for i in xrange(10 ** d, 10 ** (d + 1)):
            yield i * 10**(d + 1) + long(str(i)[::-1])

def check(n):
    return str(n) == str(n)[::-1]

def main():
    v = [i * i for i in palindromes() if check(i * i)]
    N = int(raw_input())
    for tc in xrange(1, N + 1):
        A, B = map(long, raw_input().split())
        print 'Case #%d: %d' % (tc, bisect.bisect_right(v, B) - bisect.bisect_left(v, A))

if __name__ == '__main__':
    main()