#include <fstream>
using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

long long a,b,m,fact[20],k,rez,i,n,nr;
int prime[100000],v[20];
bool c[1000005];

void ciurr();
void solve(long long a, long long b);
void submultimi();
int main()
{
    ciurr();
    cin>>n;
    for(i=1; i<=n; ++i)
    {
        cin>>a>>b;
        solve(a,b);
    }
    return 0;
}
void ciurr()
{
    c[0]=c[1]=1;
    for(int i=2; i*i<=1000000; i++)
        if(c[i]==0)
        {
            for(int j=i*i; j<=1000000; j=j+i)
                c[j]=1;
        }

    for(i=2; i<=1000000; i++)
        if(c[i]==0) prime[++k]=i;
}


void submultimi(int k,int idx)
{
    if(idx==k+1)
    {
        long long p=1;
        for(int i=1; i<=k; ++i)
            p*=fact[v[i]];

        if(k%2==0) rez=rez-a/p;
        else rez+=a/p;
    }
    else
    {
        for(int i=v[idx-1]+1; i<=nr-k+idx; ++i)
        {
            v[idx]=i;
            submultimi(k,idx+1);
        }

    }
}

void solve(long long a, long long b)
{
    ///k
    rez=0;
    int ind=1;
    nr=0;

    while(b>1 && ind<=k)
    {
        if(b%prime[ind]==0)
        {
            while(b%prime[ind]==0) b=b/prime[ind];
            fact[++nr]=prime[ind];
        }

        ind++;

    }
        if(b>1) fact[++nr]=b;

    int i=0;

    for(i=1; i<=nr; ++i)
    {
        submultimi(i,1);
    }

    cout<<a-rez<<"\n";

}