#include <stdio.h>

using namespace std;

#define MAX 1000000

bool ciur[MAX+1];
int v[MAX+1],nrp=0;

int p[20000],k=0;

void genPrimes()
{
    long long i,j;
    for(i=2;i<=MAX;i++)
        if(ciur[i]==0)
        {
            v[++nrp]=i;
            for(j=i*i;j<=MAX;j+=i)
                ciur[j]=1;
        }
}

long long sol(long long a, long long b)
{
    int i=v[1],nr=1;
    long long prod=1,s=0;

    k=0;
    while(b!=1 && i!=0)
    {
        if(b%i==0)
        {
            while(b%i==0)
                b/=i;
            p[k++]=i;
        }
        i=v[++nr];
    }
    if(i==0)
        p[k++]=b;

    for(i=0;i<(1<<k);i++)
    {
        prod=1;
        nr=0;
        for(int j=0;j<k;j++)
            if(i & (1<<j))
            {
                prod*=p[j];
                nr++;
            }
        if(nr%2==0)
            s+=a/prod;
        else
            s-=a/prod;
    }
    return s;
}

int main()
{
    FILE *fin,*fout;

    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");

    genPrimes();

    int m,i;

    fscanf(fin,"%d",&m);

    for(i=1;i<=m;i++)
    {
        long long a,b;
        fscanf(fin,"%lld%lld",&a,&b);
        fprintf(fout,"%lld\n",sol(a,b));
    }

    return 0;
}