#include<stdio.h>
#include<vector>
#include<bitset>

using namespace std;

#define plm long long
#define Max 100005
#define pb push_back

plm A,B;
vector <plm> p,nr;
bitset <Max> e;

void ciur()
{
    for(plm i=2;i<Max;++i)
        if (!e[i])
            {
            for(plm j=i*i;j<Max;j+=i)
                e[j]=1;
            p.pb(i);
            }
}

void solve()
{
    int M,semn;
    plm prod,sum;
    nr.clear();
    vector<plm>::iterator it;

    M=0;
    for(it=p.begin(); it!=p.end() && (*it)*(*it) <= B ;++it)
        if (B%(*it)==0)
            {
            nr.pb(*it);
            ++M;
            for(; B%(*it)==0 ; B/=(*it));
            }
    if (B>1)
        {
        nr.pb(B);
        ++M;
        }

    sum=0;
    for(int i=1;i<(1<<M);++i)
        {
        prod=1;
        semn=0;
        for(int j=0;j<M;++j)
            if (i&(1<<j))
                {
                semn^=1;
                prod*=nr[j];
                }
        sum += (2*semn-1)*(A/prod);
        }
    printf("%lld\n",A-sum);
}

int main()
{
    int T;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();

    scanf("%d",&T);
    for(; T ;--T)
        {
        scanf("%lld%lld",&A,&B);
        solve();
        }
    return 0;
}