#include"bits/stdc++.h"
const int M=1e7;
const int MD=1e9+7;
using namespace std;
typedef long long ll;
ll p[M];
bool ans[M];
int dig(int n)
{
int su=0;
while(n>0)
{
su+=n%10;
n=n/10;
}
return su;
}
void sieve()
{
for(int i=2;i<=1000000;i++)
{
if(ans[i]) continue;
p[i]=dig(i);
for(int j=i+i;j<=M;j+=i)
{
ans[j]=true;
p[j]+=p[i];
}
}
for(int i=1;i<=M;i++)
p[i]+=p[i-1];
}
int main() {
sieve();
int t;
cin>>t;
while(t--)
{
int l,r;
cin>>l>>r;
cout<<p[r]-p[l-1]<<endl;
}
return 0;
}
I2luY2x1ZGUiYml0cy9zdGRjKysuaCIKCmNvbnN0IGludCBNPTFlNzsKY29uc3QgaW50IE1EPTFlOSs3Owp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKbGwgcFtNXTsKYm9vbCBhbnNbTV07CmludCBkaWcoaW50IG4pCnsKCWludCBzdT0wOwoJd2hpbGUobj4wKQoJewoJCXN1Kz1uJTEwOwoJCW49bi8xMDsKCX0KCXJldHVybiBzdTsKfQp2b2lkIHNpZXZlKCkKewoJZm9yKGludCBpPTI7aTw9MTAwMDAwMDtpKyspCgl7CgkJaWYoYW5zW2ldKSBjb250aW51ZTsKCQlwW2ldPWRpZyhpKTsKCQlmb3IoaW50IGo9aStpO2o8PU07ais9aSkKCQl7CgkJICAgYW5zW2pdPXRydWU7CgkJICAgcFtqXSs9cFtpXTsKCQl9Cgl9Cglmb3IoaW50IGk9MTtpPD1NO2krKykKCXBbaV0rPXBbaS0xXTsKfQppbnQgbWFpbigpIHsKCXNpZXZlKCk7CglpbnQgdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQlpbnQgbCxyOwoJCWNpbj4+bD4+cjsKCQljb3V0PDxwW3JdLXBbbC0xXTw8ZW5kbDsKCX0KCXJldHVybiAwOwp9