#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;
void bkt(int,long long);

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;sol=0;
        d = 0;
        for(i = 1; i <= k; i++)
        {
            if(p[i]*p[i] > b)
                break;
            if(b % p[i] == 0)
            {
                F[++d]=p[i];
                while(b%p[i]==0)
                    b/=p[i];
            }

        }
        if(b>1)
            F[++d]=b;
        bkt(1,1);
        g << sol << '\n';
    }
    return 0;
}
void bkt(int poz,long long val)
{
    if(poz==d+1)
    {
        sol+=a/val;
        return;
    }
    bkt(poz+1,val);
    bkt(poz+1,val*(-F[poz]));

}