#include <bits/stdc++.h>
#define Int long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
Int A,B,i,j,k,p[20],m,n,sol,P[80000];
bitset<1000002> used;
void ciur(),solve(),bkt(Int,int,int);
int main()
{
    ciur();
    f>>m;
    for(; m; m--)
        solve();

    return 0;
}
void ciur()
{
    P[++k]=2;
    for(i=3; i<=1000; i+=2)
        if(!used[i])
        {
            P[++k]=i;
            for(j=i*i; j<=1000000; j+=2*i)
                used[j]=1;
        }
    for(; i<=1000000; i+=2)
        if(!used[i])
            P[++k]=i;

}

void solve()
{
    f>>A>>B;
    n=0;
    sol=0;
    for(i=1; i<=k&&P[i]*P[i]<=B; i++)
        if(B%P[i]==0)
        {
            p[++n]=P[i];
            while(B%P[i]==0)
                B/=P[i];
        }
    if(B>1)
        p[++n]=B;
    bkt(1,1,1);
    g<<sol<<"\n";

}

void bkt(Int produs,int poz,int par)
{
    if(poz==n+1)
    {
        if(par)
            sol+=A/produs;
        else
            sol-=A/produs;

        return;
    }
    bkt(produs,poz+1,par);
    bkt(produs*p[poz],poz+1,1-par);
}