#include <iostream>
#include <fstream>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
long long a,b,m,scad,temp=1,p[1005],it;
int ind=0,auxx,prim[80005],cont;
bool ok[1000005];
void bacK(int k)
{
    if(k==it+1)
    {
        if(!cont)return;
        if(cont%2==1) scad=scad+(a/temp);
        else scad=scad-(a/temp);
        return;
    }
    for(int x=0;x<=1;++x)
    {
        if(x)cont++,temp*=p[k];
        bacK(k+1);
        if(x)
        {
            temp/=p[k];
            cont--;
        }
    }
}
void prime()
{
    prim[++ind]=2;
    for(int i=3;i*i<=1000000;i+=2)
    {
        if(!ok[i])
        {
            prim[++ind]=i;
            auxx=i*2;
            for(int j=i*i;j<=1000000;j+=auxx)
            {
                ok[j]=1;
            }
        }
    }
    for(int i=prim[ind]+2;i<=1000000;i+=2)
    {
        if(!ok[i])prim[++ind]=i;
    }
}
int main()
{
    in>>m;
    prime();
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        it=0;
        scad=0;
        for(int j=1;j<=ind && b>=prim[j];j++)
        {
            if(b%prim[j]==0)
            {
                while(b%prim[j]==0)
                {
                    b/=prim[j];
                }
                p[++it]=prim[j];
            }
        }
        if(b>1)p[++it]=b;
        bacK(1);
        out<<a-scad<<'\n';
    }
    return 0;
}