from bisect import bisect_right as ub
l = [1, 4, 9, 121, 484]
def pal1(s):
    x = int(s[:-1] + s[::-1])
    l.append(x*x)

def pal2(s):
    x = int(s + s[::-1])
    l.append(x*x)

def prepare(x, s):
    if len(x) > 25:
        return
    for i in xrange(10):
        y = x + chr(48 + i)
        if 2*s + i*i < 10: pal1(y)
        if 2*(s + i*i) < 10:
            pal2(y)
            prepare(y, s + i*i)

for i in xrange(1, 10):
    prepare(str(i), i*i)

l2 = set(l)
l = list(l2)
l.sort()

T = int(raw_input())
for t in xrange(T):
    a,b = [int(x) for x in raw_input().split(' ')]
    print "Case #%d: %d" % (t+1, ub(l, b) - ub(l, a-1))