#include <cstdio>
#include <vector>
#define MAXN 1000001
using namespace std;
vector <int> prime;
bool ciur[MAXN];
long long div[15];
int nrdiv;
inline void desc(long long x)
{
    int i;
    long long d=prime[0];
    i=nrdiv=0;
    while(i<prime.size() && d*d<=x)
    {
        if(x%d==0)
        {
            div[nrdiv++]=d;
            while(x%d==0)
                x/=d;
        }
        d=prime[++i];
    }
    if(x>1)
        div[nrdiv++]=x;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    for(int i=2;i*i<MAXN;i++)
        for(int j=i*i;j<MAXN;j+=i)
            ciur[j]=true;
    for(int i=2;i<MAXN;i++)
        if(!ciur[i])
            prime.push_back(i);
    int t,lim,mask,nrbit;
    long long a,b,sum,prod;
    char semn;
    fscanf(fin,"%d",&t);
    for(int i=0;i<t;i++)
    {
        fscanf(fin,"%lld%lld",&a,&b);
        desc(b);lim=1<<nrdiv;sum=0;
        for(int j=1;j<lim;j++)
        {
            prod=mask=1;nrbit=0;
            for(int k=0;k<nrdiv;k++)
            {
                if(j&mask)
                    prod*=div[k],nrbit++;
                mask<<=1;
            }
            if(nrbit&1)
                semn=1;
            else
                semn=-1;
            sum+=semn*a/prod;
        }
        fprintf(fout,"%lld\n",a-sum);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}