#include <iostream>
#include <fstream>
#include <map>
#include <vector>

using namespace std;

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

int prim[1000005] , n , d[80003] , cnt , k , j , t;
long long a , b;

void ciur ()
{
    for (int i = 2 ; i <= 1000000 ; i++)
    {
        if (prim[i] == 0)
        {
            d[++cnt] = i;
           for (int j = 2 * i ; j <= 1000000 ; j = j + i)
               prim[j] = 1;
        }
    }
}

int solve (int a , int b)
{
    int ok = 0 , cnt = 0;;
    map <unsigned long long , int >m;
    vector <long long>fac;
    for (k = 1 ; 1LL* d[k] * d[k] <= b ; k++)
    {
        ok = 0;
        while (b % d[k] == 0)
            b = b / d[k] , ok = 1;
        if (ok == 1)
            fac.push_back (d[k]);
    }
    if (b > 1)
        fac.push_back (b) , b = 1;
    for (j = 0 ; j < fac.size () ; j++)
    {
        for (long long i = fac[j] ; i <= a ; i = i + fac[j])
            if (m[i] == 0)
            cnt++ , m[i] = 1;
    }
    return a - cnt;
}


int main()
{
    ciur ();
    f >> t;
    while (t)
    {
        f >> a >> b;
        g << solve (a , b) << '\n';
        t--;
    }
    return 0;
}