icpc

int t;
   scanf("%d",&t);
   for(int j=1; j<=t; j++)
   {
        int n,k, ans, tmp=0;
        scanf("%d %d",&n,&k);
         int c = ceil(1/k*1.0);
        for( int i=1; i<=n; i++)
        {
            ans = pow(i,c);
            if(i%ans==0)tmp++;
        }
        printf("Case #%d: %d\n",j,tmp);
   }