#include <stdio.h>

#define MAX 100005
#define mod 1000000009
int data[MAX];

void generate(){
	for(int i=2;i<MAX;i++){
		data[i] = data[i-2]%mod + data[i-1]%mod;
	}
}

int main(){
	int tc, temp;
	data[0] = 0;
	data[1] = 1;
	generate();
	scanf("%d", &tc);
	for(int i=1;i<=tc;i++){
		scanf("%d", &temp);
		printf("Case #%d: %d\n", i, (data[temp+2]-1)%mod);
	}
	return 0;
}