/*
//(3+5^1/2)^n 주기 찾기
#include <stdio.h>
#define MOD 1000

int arr[MOD];

int main() {

    int flag=0; //주기 존재 유무
    arr[0]=2;
    arr[1]=6;

    for(int i=2; i<MOD; i++) {

        //a_n+2 = 6*a_n+1 - 4*a_n : 뉴턴 항등식
        arr[i]=6*arr[i-1]-4*arr[i-2];

        //음수 보정
        arr[i]=(arr[i]+10000)%1000;

        for(int j=0; j<i-1; j++) {
            if(arr[j] == arr[i-1] && arr[j+1] == arr[i]) {
                printf("주기 시작 : %d, 끝 : %d", j, i-2);
                flag=1; break;
            }
        }
        if(flag) break; 
    }

    if(flag==0) printf("주기 없음");
}
//-> 1, 2, [3,102]반복 [103, 205]
*/

#include <stdio.h>

int arr[500];

void f() {
    for(int i=2; i<500; i++) {
        arr[i]=6*arr[i-1]-4*arr[i-2];
        arr[i]=(arr[i]+10000)%1000;
    }
}

int main() {

    arr[0]=2;
    arr[1]=6;

    f();
    
    int T;
    scanf("%d", &T);

     /*
    //debuging : 배열 확인
    for(int i=3; i<102; i++) {
        printf("%d : %d, %d, %d\n", i, arr[i], arr[i+100], arr[i+200]);
    }
    */
    
    for(int i=1; i<=T; i++) {
        long long n;
        scanf("%lld", &n);
        
        if(n>=103) {
            if(n%100==0) n=100;
            else if(n%100==1) n=101;
            else if(n%100==2) n=102;
            else n%=100;
        }
        printf("Case #%d: %03d\n", i, arr[n]-1);
    }
}