import java.io.*;


public class Main
{
    int N,n;
    int mod=1000;
    long a[][];



    static BufferedReader br;
    //static Scanner sc;
    static PrintWriter p;



    public static void main(String[] args) throws Exception
	{
        //sc=new Scanner(new File("C-small-practice.in"));
        br=new BufferedReader(new FileReader("C-small-practice.in"));
        p=new PrintWriter(new FileWriter("output.txt"));
        new Main().call();
        }



    void call() throws IOException
       	{
        int i;
        a=new long[2][2];        
        N=getInt();
		for(i=1;i<=N;i++)
		{   int r;
                    a[0][0]=6;
                    a[0][1]=-4;
                    a[1][0]=1;
                    a[1][1]=0;
                    r=multi(getInt());
                    if(r==0)r=999;
                    else r--;
                    p.printf("Case #%d: %03d",i,r);
                    p.println();
		}
		br.close();
		p.close();
        }




        int multi(int n)
        {
            long temp[][]=new long[2][2];
            temp=a;
            if(n==0)
                return 3;
            else if(n==1)
                return 6;
            else
            {

                for(int i=1;i<=n-2;i++)
                    temp=premulti(temp);
            
                return (int)((temp[1][0]*28+temp[1][1]*6)%mod);
            }
             
        }
        long[][] premulti(long temp[][])
        {
            long t[][]=new long [2][2];
            t[0][0]=((temp[0][0])*(a[0][0])+(temp[0][1])*(a[1][0]));
            t[0][1]=((temp[0][0])*(a[0][1])+(temp[0][1])*(a[1][1]));
            t[1][0]=((temp[1][0])*(a[0][0])+(temp[1][1])*(a[1][0]));
            t[1][1]=((temp[1][0])*(a[0][1])+(temp[1][1])*(a[1][1]));
            return t;
        }

        int getInt() throws IOException
		{
                return Integer.parseInt(br.readLine());
        }
	
}