#include <fstream>
#include <cstring>

using namespace std;

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

int n, i, j;
long long a, b, ans;
bool ok, used[10000005];

int main()
{
   f >> n;
    while (n --)
    {
        f >> a >> b;
        memset(used, 0, sizeof(used));
        ans = 0, ok = false;
         for (i=2; i*i<=b; i++)
         {
             if (b % i == 0)
             {
                 ok = true;
                  for (j=i; j<=a; j+=i)
                      if (!used[j])
                      {
                          used[j] = 1;
                          ans ++;
                      }

                  for (j=b/i; j<=a; j+=b/i)
                       if (!used[j])
                       {
                          used[j] = 1;
                          ans ++;
                       }
             }
         }
       if (!ok)
        for (j=b; j<=a; j+=b)
           ans ++;
       g << a-ans << '\n';
    }
    return 0;
}