/*  2022/2023 Regional
    International Collegiate Programming Contest

    Problem ?
    Distinct Parity
    M. K. Furon.                    2022-12-02.                       */




#include  <stdio.h>
#include  <stdlib.h>

#define   MAXVALUE   10000000




int answer, high, i, iocount, j, low;
char pcount[(MAXVALUE + 1)];




void abend (char *message)
{
(void) fputs (message, stderr);
(void) fputc ('\n', stderr);
exit (4);
}




int main (int argc, char *argv[], char *envp[])
{
   for (i = 2; i <= MAXVALUE; i++)
      pcount[i] = (char) 0;
/*  Run the sieve to determine the number of distinct prime factors
    for each possible value.                                          */
   for (i = 2; i <= MAXVALUE; i++)
      {
         if (!pcount[i])                  /*  If zero factor count, prime   */
            for (j = i; j <= MAXVALUE; j += i)
               pcount[j]++;
      }
   int cnt ;
   scanf("%d", &cnt) ;
   for (int trial=0; trial<cnt; trial++) {
      scanf ("%d %d", &low, &high) ;
      answer = 0;
   /*  Scan through the values between low and high, inclusive.  Add
       one for every even factor count, subtract one for every odd
       factor count.                                                  */
      for (i = low; i <= high; i++)
         answer += (pcount[i] & 1) ? (-1) : 1;
      (void) printf ("%d\n", answer);
   }
}