#include <iostream>
#include <fstream>
#define N 1000000

using namespace std;

int nr;
long long div1[20],sum=0;
bool ok[20],prim[1111111];
int p[1000000],nrp;
void ciur()
{
    int i,j;
    prim[1]=true;
    for(i=2;i*i<=N;++i)
    {
        if(prim[i]==true)
            continue;
        for(j=i;i*j<=N;++j)
        {
            prim[i*j]=true;
        }
    }
    for(i=1;i<=N;++i)
        if(prim[i]==false)
            p[++nrp]=i;
}

void descompune(long long x)
{
    int i=1;
    nr=0;
    while(x!=1 && i<=nrp)
    {
        if(x%p[i]==0)
        {
            div1[++nr]=p[i];
            while(x%p[i]==0)
                x/=p[i];
        }
        ++i;
    }
    if(x!=1)
        div1[++nr]=x;
}

void bkt(int pos ,long long a)
{
    int i,k=0;
    long long aux=1;
    if(pos==nr)
    {
        for(i=1;i<=nr;++i)
        {
            if(ok[i])
            {
                ++k;
                aux*=div1[i];
            }
        }
        if(k%2==1)
        {
            sum-=a/aux;
        }
        else
            sum+=a/aux;
        return;
    }
    ok[pos+1]=true;
    bkt(pos+1,a);
    ok[pos+1]=false;
    bkt(pos+1,a);
}

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    int m,i;
    long long a,b;
    in>>m;
    ciur();
    for(i=1;i<=m;++i)
    {
        in>>a>>b;
        sum=0;
        descompune(b);
        bkt(0,a);
        out<<sum<<"\n";
    }
    return 0;
}