/*

     题意：b+1，b+2，...，a 所有数的素数个数和

     DP+埃氏筛法：dp[i] 记录i的素数个数和，若i是素数，则为1；否则它可以从一个数乘以素数递推过来

                     最后改为i之前所有素数个数和，那么ans = dp[a] - dp[b]；

     详细解释：http://blog.csdn.net/catglory/article/details/45932593

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = 5e6 + ;

 const int INF = 0x3f3f3f3f;

 int prime[MAXN];

 bool is_prime[MAXN];

 ll dp[MAXN];

 int seive(void)

 {

     for (int i=; i<=5e6; ++i)    is_prime[i] = true;

     is_prime[] = is_prime[] = false;

     int p = ;

     for (int i=; i<=5e6; ++i)

     {

         if (is_prime[i])

         {

             prime[++p] = i;

             for (int j=*i; j<=5e6; j+=i)    is_prime[j] = false;

         }

     }

     return p;

 }

 void solve(void)

 {

     int p = seive ();

     for (int i=; i<=5e6; ++i)

     {

         if (is_prime[i])    {dp[i] = ;    continue;}

         for (int j=; j<=p; ++j)

         {

             if (i % prime[j] == )

             {

                 dp[i] = dp[i/prime[j]] + ;    break;

             }

         }

     }

     for (int i=; i<=5e6; ++i)    dp[i] += dp[i-];

 }

 int main(void)        //Codeforces Round #304 (Div. 2) D. Soldier and Number Game

 {

     solve ();

     int t;    scanf ("%d", &t);

     while (t--)

     {

         int a, b;

         scanf ("%d%d", &a, &b);

         printf ("%I64d\n", dp[a] - dp[b]);

     }

     return ;

 }

 /*

 3

 3 1

 6 3

 5000000 4999995

 */