#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int BMAX=1000005;
const short BITMAX=22;
bitset<BMAX>ciur;
int prime[BMAX],k,ex[BITMAX],nexp,biti[BITMAX],query;
inline void CIUR()
{
    ciur[1]=1;
    for(int i=4;i<=BMAX-5;i+=2)
        ciur[i]=1;
    for(int i=3;i*i<=BMAX-5;i+=2)
        if(!ciur[i])
            for(int j=i*i;j<=BMAX-5;j+=2*i)
                ciur[j]=1;
    k=1;
    prime[k]=2;
    for(int i=3;i<=BMAX-5;i+=2)
        if(!ciur[i])
    {
        ++k;
        prime[k]=i;
    }
}
inline void D(long long x)
{
    nexp=0;
    int i=1,d;
    d=prime[i];
    while(i<=k && 1LL*d*d<=x && x>1)
    {
        if(x%d==0)
        {
            ++nexp;
            ex[nexp]=d;
            while(!(x%d))
                x/=d;
        }
        i++;
        d=prime[i];
    }
    if(x>1)
    {
        ++nexp;
        ex[nexp]=x;
    }
}
inline void R()
{
    for(int i=1;i<=20;i++)
        biti[i]=0;
}
inline long long SOLVE(long long dw)
{
    int c,i;
    long long sol=1;
    biti[1]=1;
    c=nexp+1;
    while(!biti[c])
    {
        int nr1=0;
        long long s=1;
        for(i=1;i<=nexp;i++)
        {
            nr1+=biti[i];
            if(biti[i])
                s=1LL*s*ex[i];
        }
        if(nr1%2)
            sol+=(dw/s);
        else sol-=(dw/s);
        for(i=1;biti[i];i++)
                biti[i]=0;
        biti[i]=1;
    }
    return sol;
}
int main()
{
    CIUR();
    fin>>query;
    while(query--)
    {
        long long q1,q2,s;
        fin>>q1>>q2;
        D(q2);
        s=SOLVE(q1);
        fout<<q1-s+1<<"\n";
        R();
    }
    fin.close();
    fout.close();
    return 0;
}