#include <fstream>

using namespace std;

ifstream f ("pinex.in");
ofstream g ("pinex.out");

int n, a, b, cnt;
int i, j, v[105], k;
bool ok;

bool check (int nr)
{
  for (int i=1; i<=k; i++)
    if (nr % v[i] == 0)
      return false;
  return true;
}

int main()
{
 f >> n;
  while (n --)
  {
     f >> a >> b;
     cnt = k = 0;
     ok = false;

      for (i=2; i*i<=b; i++)
      {
         if (b % i == 0)
         {
            ok = true;
            for (j=i; j<=a; j+=i)
            {
                if (k == 0)
                  cnt ++;
                else if (check(j)) cnt ++;
            }
            k ++, v[k] = i;

             if (i * i < b)
             {
                 for (j=b/i; j<=a; j+=b/i)
                 {
                     if (k == 0)
                       cnt ++;
                     else if (check(j)) cnt ++;
                 }
               k ++, v[k] = b/i;
             }
         }
      }

      if (!ok)
        for (j=b; j<=a; j+=b) cnt ++;

    g << a - cnt << '\n';
  }
    return 0;
}