#include <stdio.h>
int t,p,n,ans,k=0;

int main(void){
	while (scanf ("%d%d",&p,&n)!=EOF&&n){
               ans=1;
               while (n>0)ans=(ans*(n%p+1))%10000,n/=p;
               printf ("Case %d: %04d\n",++k,ans);
               }
	return 0;
	}