#include <iostream>
#include <stdio.h>

using namespace std;

#define MMAX 500
#define RADMMAX 23

int ciur[MMAX + 1];
int vec_prime[RADMMAX];

int main()
{
    FILE *fin, *fout;
    int num_m, num_a, num_b, rez, poz, ind1, ind2, sum, x, divi, ind;

    ciur[0] = ciur[1] = 1;
    for ( divi = 2; divi * divi <=  MMAX; divi++ ) {
      if ( ciur[divi] == 0 ) {
        for ( ind = divi * divi; ind <= MMAX; ind += divi )
          ciur[ind] = 1;
      }
    }

    fin = fopen( "pinex.in", "r" );
    fscanf( fin, "%d", &num_m );
    fout = fopen( "pinex.out", "w" );

    for ( ind = 0; ind < num_m; ind++ ) {

      fscanf( fin, "%d%d", &num_a, &num_b );
      sum = rez = poz = 0;
      x = 1;
      divi = 2;
      while ( divi * divi <= num_b ) {
        if ( ciur[divi] == 0 ) {
            vec_prime[poz] = divi;
            poz++;
            sum = sum + (num_a / divi);
            x = x * divi;
        }
        divi++;
      }
      printf( "%d ", sum );
      sum = sum + (num_a / x);
      x = 0;
      for ( ind1 = 0; ind1 < poz - 1; ind1++ ) {
        for ( ind2 = ind1 + 1; ind2 < poz; ind2++ ) {
          x = vec_prime[ind1] * vec_prime[ind2];
          sum = sum - (num_a / x);
        }
      }
      rez = num_a - sum;
      printf( "\n" );
      fprintf( fout, "%d\n", rez );

    }
    fclose( fin );
    fclose( fout );
    return 0;
}