#include <fstream>
#include <bitset>

using namespace std;

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

long long p[80000], a, b, F[20000], sol;
int i, j, k, d, m, n;
bitset<1000010> P;

int main()
{
    p[++k] = 2;
    for(i = 3; i*i < 1e6; i+=2)
        if(!P[i])
        {
            p[++k] = i;
            for(j = i*i; j < 1e6; j+=2*i)
                P[j] = 1;
        }
    for(; i < 1e6; i+=2)
        if(!P[i])
            p[++k] = i;

    f >> m;
    F[1]=1;
    for(; m; m--)
    {
        f >> a >> b;
        d = 1;
        for(i = 1; i <= k; i++)
        {
            if(p[i]*p[i] > b)
                break;
            if(b % p[i] == 0)
            {
                for(j = 1; j <= d; j++)
                    F[d+j] = F[j] * (-p[i]);
                d *= 2;
                while(b%p[i]==0)
                    b/=p[i];
            }

        }
        if(b>1)
        {
            for(j = 1; j <= d; j++)
                F[d+j] = F[j] * (-b);
            d *= 2;
        }
        for(j = 1, sol = 0; j <= d; j++)
            sol += a/F[j];
        g << sol << '\n';
    }
    return 0;
}