#include <stdio.h>
#include <math.h>
 long long int prime(long  long int n) {
if(n == 1) return 0;
if (n == 2) return 1;
else if (n % 2 == 0) return 0;
else {
 long long int i;
for(i = 3; i * i <= n; i = i + 2) {
if(n % i == 0) return 0;
}


}
return 1;

}
main()
{
    long long int T,t,a,b,i,count,j,value,n;
    scanf("%lld",&T);
    for(t = 1; t <= T; t++) {
        count = 0;
        value = 0;
    scanf("%lld %lld",&a,&b);
    for(i = a; i <= b; i++) {
     j = 2;
     while (j <= i) {

       if(1 == prime(j) && 0 == prime(i)) {
       for(n = 1; value <= i; n++) {
       value = pow(j,n);
       if(value == i)
       {count++;

       }

       }

       }
       if(value == i) break;
       if(value != i) j++;

     }

        }
        printf("Case %lld: %lld\n",t,count);

    }
    return 0;

    }