#include <bits/stdc++.h>

using namespace std;

ofstream fout("pinex.out");

long long Q,A,B,nrf,sol;
long long fact[103];
bitset<103>a;

void Descompun(long long N)
{
    long long d;
    nrf=0;
    d=2;
    while(N>1)
    {
        if(N%d==0)
        {
            fact[++nrf]=d;
            while(N%d==0)
                N/=d;
        }
        if(d==2)    d++;
        else    d+=2;
    }
    //for(i=1;i<=nrf;++i)
        //cout<<fact[i]<<" ";
    //cout<<"\n";
}

void Cnt()
{
    long long p,i,cnt;
    //for(i=1;i<=nrf;++i)
        //cout<<a[i]<<" ";
    //cout<<"\n";
    p=1;
    cnt=0;
    for(i=1;i<=nrf;++i)
        if(a[i]==1)
        {
            cnt++;
            p*=fact[i];
        }
    if(cnt%2==1)
    {
        sol+=(A/p);
        //cout<<p<<"   p\n";
    }
    else
        if(p!=1)
            sol-=(A/p);
}

void Solve()
{
    long long i,j;
    //cout<<nrf<<":\n";
    for(i=0;i<=nrf;++i)
        a[i]=0;
    while(a[0]==0)
    {
        for(i=nrf;i>=0;--i)
            if(a[i]==0)
            {
                Cnt();
                a[i]=1;
                for(j=i+1;j<=nrf;++j)
                    a[j]=0;
                i=-1;
            }
    }
    //cout<<"\n\n";
}

int main()
{
    long long i;
    ifstream fin("pinex.in");
    fin>>Q;
    for(i=1;i<=Q;++i)
    {
        fin>>A>>B;
        Descompun(B);
        sol=0;
        Solve();
        sol=A-sol;
        fout<<sol<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}