from sys import stdin
from math import sqrt, floor

num = int(stdin.readline())
q = 3 + sqrt(5)
for i in range(num):
    n = int(stdin.readline())
    r = 1
    for j in range(n):
        r = r*q
        if r >= 1000:
            r -= floor(r/1000)*1000
    print "Case #%d: %0d" % (i+1, int(floor(r)))