nowB*=fac[idx][0];
}
fac[idx][1]=temp;
}
//以上搜索B
LL slove(){
v.clear();
get_fact(A-1);
get_fact(A+1);
get_union();
ans=0;
dfsB(0,1);
return ans;
}
int t,cas=0;
Prime();
inverse_4=Get_inverse(4);
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d",&A,&c);
printf("Case %d: ",++cas);
if(A==1) printf("%I64d\n",c);
else
printf("%I64d\n",slove());
}
return 0;
}