/*
AUTHOR : Chandan Agrawal
College : Poornima College of Engg. jaipur, Raj
Mail : chandanagrawal23@gmail.com
___ _ _ __ _ _ ____ __ _ _
/ __)( )_( ) /__\ ( \( )( _ \ /__\ ( \( )
( (__ ) _ ( /(__)\ ) ( )(_) )/(__)\ ) (
\___)(_) (_)(__)(__)(_)\_)(____/(__)(__)(_)\_)
*/
#include<bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<cstdio>
#define MAX 10000001
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<unordered_map>
#define ll long long
#define ld long double
#define lli long long int
#define pb push_back
#define INF 1000000000
#define mod 1000000007
#define MOD 1000000007
//#define mp make_pair
#define loop(i,n) for (lli i = 0; i < n; i++)
#define FOR(i,a,b) for (lli i = a; i < b; i+=1)
#define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
#define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define mii map<lli,lli>
#define vi vector<lli>
#define vvi vector<lli>
#define itr :: iterator it
#define print(x) printf("%lli\n",x);
#define print2(x,y) printf("%lli %lli\n",x,y);
#define print3(x,y,z) printf("%lli %lli %lli\n",x,y,z);
#define scan(x) scanf("%lli",&x);
#define scan2(x,y) scanf("%lli %lli",&x,&y);
#define scan3(x,y,z) scanf("%lli %lli %lli",&x,&y,&z);
#define printarr(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
#define scanarr(a,n) for(lli i=0;i<n;i++) scan(a[i]);
// cout<<fixed<<setprecision(6)<<value;
//#define deb(x) cout<<#x<<" "<<x<<endl;
using namespace std;
lli cntodd(lli n){
lli res = 1;
while (n % 2 == 0)
n = n / 2;
for (lli i = 3; i <= sqrt(n); i++)
{
lli cnt = 0;
while (n % i == 0) {
cnt++;
n = n / i;
}
res *= cnt+1;
}
if (n >= 2)
res *= (2);
return res;
}
lli cnteven(lli n){
lli res = 1;
lli cnttw =0;
while (n % 2 == 0){
n = n / 2;
cnttw++;
}
if(n==1) return cnttw;
for (lli i = 3; i <= sqrt(n); i++)
{
lli cnt = 0;
while (n % i == 0) {
cnt++;
n = n / i;
}
res = res*(cnt+1);
}
if (n >= 2)
res = res*(2);
return res*cnttw;
return res;
}
void solve(){
lli l,r,bob,alice,cnt=0;
cin>>l>>r;
for(lli i=l;i<=r;i++){
if(i%2==0){
bob=cnteven(i);
alice = cntodd(i);
//cout<<"\n";
//cout<<bob<<" "<<alice;
if (abs(bob-alice) <=2) cnt++;
}
else{
bob = 0;
alice = cntodd(i);
//cout<<"\n";
//cout<<bob<<" "<<alice;
if(alice<=2)
cnt++;
}
}
cout<<cnt;
}
int main(){
fastIO
lli t;
cin>>t;
loop(i,t){
cout<<"Case #"<<i+1<<": ";
solve();
cout<<endl;
}
}
LyoKIApBVVRIT1IgOiBDaGFuZGFuIEFncmF3YWwKQ29sbGVnZSA6IFBvb3JuaW1hIENvbGxlZ2Ugb2YgRW5nZy4gamFpcHVyLCBSYWoKTWFpbCA6IGNoYW5kYW5hZ3Jhd2FsMjNAZ21haWwuY29tCiAKIAogIF9fXyAgXyAgIF8gICAgX18gICAgXyAgXyAgX19fXyAgICBfXyAgICBfICBfCiAvIF9fKSggKV8oICkgIC9fX1wgICggXCggKSggIF8gXCAgL19fXCAgKCBcKCApCiggKF9fICApIF8gKCAgLyhfXylcICApICAoICApKF8pICkvKF9fKVwgICkgICgKIFxfX18pKF8pIChfKShfXykoX18pKF8pXF8pKF9fX18vKF9fKShfXykoXylcXykKIAogCiAKIAoqLwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGZhc3RJTyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApO2NvdXQudGllKDApOwojaW5jbHVkZTxjc3RkaW8+CiNkZWZpbmUgTUFYIDEwMDAwMDAxCiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8c2V0PgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxzdGFjaz4KI2luY2x1ZGU8c3RyaW5nPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGZ1bmN0aW9uYWw+CiNpbmNsdWRlPGlvbWFuaXA+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNhc3NlcnQ+CiNpbmNsdWRlPHVub3JkZXJlZF9tYXA+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBsbGkgbG9uZyBsb25nIGludAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIElORiAxMDAwMDAwMDAwCiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwovLyNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgbG9vcChpLG4pIGZvciAobGxpIGkgPSAwOyBpIDwgbjsgaSsrKQojZGVmaW5lIEZPUihpLGEsYikgZm9yIChsbGkgaSA9IGE7IGkgPCBiOyBpKz0xKQojZGVmaW5lIGxvb3BfcmV2KGksbikgZm9yIChsbGkgaSA9IG4tMTsgaSA+PSAwOyBpLS0pCiNkZWZpbmUgRk9SX1JFVihpLGEsYikgZm9yIChsbGkgaSA9IGE7IGkgPj0gYjsgaS0tKQojZGVmaW5lIGFsbCh2KSB2LmJlZ2luKCksdi5lbmQoKQojZGVmaW5lIHBpaSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgbWlpIG1hcDxsbGksbGxpPgojZGVmaW5lIHZpIHZlY3RvcjxsbGk+CiNkZWZpbmUgdnZpIHZlY3RvcjxsbGk+CiNkZWZpbmUgaXRyIDo6IGl0ZXJhdG9yIGl0CiNkZWZpbmUgcHJpbnQoeCkgcHJpbnRmKCIlbGxpXG4iLHgpOwojZGVmaW5lIHByaW50Mih4LHkpIHByaW50ZigiJWxsaSAlbGxpXG4iLHgseSk7CiNkZWZpbmUgcHJpbnQzKHgseSx6KSBwcmludGYoIiVsbGkgJWxsaSAlbGxpXG4iLHgseSx6KTsKI2RlZmluZSBzY2FuKHgpIHNjYW5mKCIlbGxpIiwmeCk7CiNkZWZpbmUgc2NhbjIoeCx5KSBzY2FuZigiJWxsaSAlbGxpIiwmeCwmeSk7CiNkZWZpbmUgc2NhbjMoeCx5LHopIHNjYW5mKCIlbGxpICVsbGkgJWxsaSIsJngsJnksJnopOwojZGVmaW5lIHByaW50YXJyKGEsbikgZm9yKGxsaSBpPTA7aTxuO2krKykgICBjb3V0PDxhW2ldPDwiICI7ICAgIGNvdXQ8PCJcbiI7CiNkZWZpbmUgc2NhbmFycihhLG4pIGZvcihsbGkgaT0wO2k8bjtpKyspICAgIHNjYW4oYVtpXSk7Ci8vIGNvdXQ8PGZpeGVkPDxzZXRwcmVjaXNpb24oNik8PHZhbHVlOwovLyNkZWZpbmUgZGViKHgpIGNvdXQ8PCN4PDwiICI8PHg8PGVuZGw7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKIAogCmxsaSBjbnRvZGQobGxpIG4pewoJbGxpIHJlcyA9IDE7Cgl3aGlsZSAobiAlIDIgPT0gMCkKCQluID0gbiAvIDI7CiAKCWZvciAobGxpIGkgPSAzOyBpIDw9IHNxcnQobik7IGkrKykKCXsKCQlsbGkgY250ID0gMDsKCQl3aGlsZSAobiAlIGkgPT0gMCkgewoJCQljbnQrKzsKCQkJbiA9IG4gLyBpOwoJCX0KCQlyZXMgKj0gY250KzE7Cgl9CglpZiAobiA+PSAyKQoJCXJlcyAqPSAoMik7CglyZXR1cm4gcmVzOwp9CiAKbGxpIGNudGV2ZW4obGxpIG4pewoJbGxpIHJlcyA9IDE7CglsbGkgY250dHcgPTA7Cgl3aGlsZSAobiAlIDIgPT0gMCl7CgkJbiA9IG4gLyAyOwoJCWNudHR3Kys7Cgl9CglpZihuPT0xKSByZXR1cm4gY250dHc7CiAKCWZvciAobGxpIGkgPSAzOyBpIDw9IHNxcnQobik7IGkrKykKCXsKCQlsbGkgY250ID0gMDsKCQl3aGlsZSAobiAlIGkgPT0gMCkgewoJCQljbnQrKzsKCQkJbiA9IG4gLyBpOwoJCX0KCQlyZXMgPSByZXMqKGNudCsxKTsKCX0KCWlmIChuID49IDIpCgkJcmVzID0gcmVzKigyKTsKCXJldHVybiByZXMqY250dHc7CiAKcmV0dXJuIHJlczsKfQogCiAKIAogCiAKIAp2b2lkIHNvbHZlKCl7CmxsaSBsLHIsYm9iLGFsaWNlLGNudD0wOwpjaW4+Pmw+PnI7CmZvcihsbGkgaT1sO2k8PXI7aSsrKXsKICAgIGlmKGklMj09MCl7CiAgICAgICAgYm9iPWNudGV2ZW4oaSk7CiAgICAgICAgYWxpY2UgPSBjbnRvZGQoaSk7CgkJLy9jb3V0PDwiXG4iOwoJCS8vY291dDw8Ym9iPDwiICI8PGFsaWNlOwogICAgICAgIGlmIChhYnMoYm9iLWFsaWNlKSA8PTIpIGNudCsrOwogICAgfQogICAgZWxzZXsKCQkJYm9iID0gMDsKICAgICAgICAgICAgYWxpY2UgPSBjbnRvZGQoaSk7CgkJLy9jb3V0PDwiXG4iOwoJCS8vY291dDw8Ym9iPDwiICI8PGFsaWNlOwogICAgICAgICAgICBpZihhbGljZTw9MikKICAgICAgICAgICAgICAgIGNudCsrOwogICAgfQp9CmNvdXQ8PGNudDsKfQogCmludCBtYWluKCl7CmZhc3RJTwpsbGkgdDsKY2luPj50Owpsb29wKGksdCl7CmNvdXQ8PCJDYXNlICMiPDxpKzE8PCI6ICI7CnNvbHZlKCk7CmNvdXQ8PGVuZGw7Cn0KIAp9