#include <fstream>
#define intt long long
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long sol,v[10000005],cnt; bool c[10000005];
void ciur()
{   c[1]=1;
    int i,j;
    for(i=2;i<=10000005;++i)
    {
        if(c[i]==0)
        {
            for(j=i*2;j<=10000005;j+=i)
            c[j]=1;
        }
    }
}
void solve(intt b)
{
    intt i; cnt=1;
    for(i=1;i*i<=b;++i)
    {
        if(b%i==0){
            if(c[i]==0){
        v[cnt]=i,++cnt;}
            if(c[b/i]==0)
            v[cnt]=b/i,++cnt;
        }
    }
    if((i-1)*(i-1)==b && c[i-1]==0)
    --cnt,v[cnt]=0;
}

long long tot(intt a)
{
    intt i;
    long long s=0;
    for(i=1;i<cnt;++i)
    s+=a/v[i];
    return s;
}
long long pinex(intt a,intt b)
{
    long long scad=0,i,j,s=0,k=0,ans=0,n=0;
    solve(b);
    s=tot(a);
for(long long i=1;i<(1<<cnt);i++)
    {
        long long nr=0, p=1;
        for(long long j=0;j<cnt;j++)
            if((1<<j)&i)
                p=p*v[j+1], nr++;
        if(nr%2==0 && p)
            n=n-a/p;
        else if(p)
            n=n+a/p;
    }
    return a-n;
}
int main()
{
    intt n,a,i,b;
    cin>>n;
    ciur();
    for(i=1;i<=n;++i)
    {
        cin>>a>>b;
        cout<<pinex(a,b)<<'\n';
    }
    return 0;
}