#include <iostream>
#include <fstream>
#include <math.h>
#define MAX 1000005
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long a,b,factor[35],ans;
int prim[MAX],nrp,n,nrf;
bool ciur[MAX];
void prelucrare()
{
    prim[++nrp]=2;
    for(int i=4; i<=MAX-5; i+=2)
        ciur[i]=1;
    for(int i=3; i<=MAX-5; i+=2)
        if(ciur[i]==0)
        {
            prim[++nrp]=i;
            for(int j=2*i; j<=MAX-5; j+=i)
                ciur[j]=1;
        }
}
void factor_prim()
{
    int d=1;
    nrf=0;
    while(b!=1&&d<=nrp)
    {
        if(b%prim[d]==0)
            factor[++nrf]=prim[d];
        while(b%prim[d]==0)b/=prim[d];
        ++d;
        if(b!=1&&prim[d]>sqrt(b))factor[++nrf]=b,b=1;
    }
}
void solve()
{
    factor_prim();
    ans=0;
    for(int i=1; i<(1<<nrf); ++i)
    {
        long long prod=1,nr=0;
        for(int j=0; j<nrf; ++j)
            if((1<<j)&i)
            {
                prod= 1LL*prod*factor[j+1];
                ++nr;
            }
        if(nr%2==0)
            ans=1LL*(ans-a/prod);
        else
            ans=1LL*(ans+a/prod);
    }
    ans=a-ans;
}
void write()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>a>>b;
        solve();
        g<<ans<<'\n';
    }
}
int main()
{
    prelucrare();
    write();
    return 0;
}