#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,p[(int)1e6+10],pmax;
long long sol,a,b;
bitset<(int)1e6+10> B;
vector<long long> v;
int main()
{
    f>>n;
    p[0]=2;
    for(i=3;i<=1000;i+=2)
        if(!B[i])
        {
            p[++k]=i;
            for(j=i*i;j<=1000000;j+=2*i)
                B[j]=1;
        }
    for(;i<=1000000;i++)
        if(!B[i])
            p[++k]=i;
    for(;n;n--)
    {
        v.resize(0);
        f>>a>>b;
        for(i=0;i<=k;i++)
        {
            if(p[i]*p[i]>b)
                break;
            if(b%p[i])
                continue;
            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);
}