#include <bits/stdc++.h>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
void bkt(int,long long);
int n,i,j,k,pmax;
long long sol,a,b;
bitset<1000010> B;
vector<long long> v,p;
int main()
{
    f>>n;
    p.push_back(2);
    for(i=3;i<=1000;i+=2)
        if(!B[i])
        {
            p.push_back(i);
            for(j=i*i;j<=1000000;j+=2*i)
                B[j]=1;
        }
    for(;i<=1000000;i+=2)
        if(!B[i])
            p.push_back(i);
    k=p.size();
    for(;n;n--)
    {
        v.resize(0);
        f>>a>>b;
        for(i=0;i<k&&p[i]*p[i]<=b;i++)
        if(b%p[i]==0)
        {
            v.push_back(p[i]);
            while(b%p[i]==0)
                b/=p[i];
        }
        if(b>0)
            v.push_back(b);
        sol=0;
        pmax=v.size();
        bkt(0,1);
        g<<sol<<'\n';
    }
    return 0;
}
void bkt(int poz,long long prod)
{
    if(poz==pmax)
    {
        sol+=a/prod;
        return ;
    }
    bkt(poz+1,prod);
    bkt(poz+1,-v[poz]*prod);
}