#include <bits/stdc++.h>
#define nmax 1000005
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset<nmax>ciur;
int baze[20],k,lg,teste,biti[20];
long long a,b,prime[nmax/5];
inline void Ciur()
{
    int i,j;
    ciur[1]=1;
    for(i=4; i<=nmax; i+=2)
        ciur[i]=1;
    for(i=3; i*i<=nmax; i+=2)
        if(!ciur[i])
            for(j=i*i; j<=nmax; j+=2*i)
                ciur[j]=1;
    k=1;
    prime[k]=2;
    for(i=3; i<=nmax; i+=2)
        if(!ciur[i])
            prime[++k]=i;
}
inline void Descompunere(long long x)
{
    int i=1,d;
    lg=0;
    d=prime[i];
    while(x>1 && (1LL*d*d)<=x && i<=k)
    {
        if(x%d==0)
        {
            baze[++lg]=d;
            while(x%d==0)
                x/=d;
        }
        i++;
        d=prime[i];
    }
    if(x>1)
        baze[++lg]=x;
}
inline long long Generare(long long t)
{
    int i,pas,nr;
    long long sol=0,s;
    for(i=1; i<=20; i++)
        biti[i]=0;
    nr=lg+1;
    biti[1]=1;
    while(!biti[nr])
    {
        s=1;
        pas=0;
        for(i=1; i<=lg; i++)
            if(biti[i])
            {
                s=1LL*s*baze[i];
                pas++;
            }
        if(pas%2)
            sol+=t/s;
        else
            sol-=t/s;
        for(i=1; biti[i]; i++)
            biti[i]=0;
        biti[i]=1;
    }
    return sol;
}
void Rezolvare()
{
    int i;
    fin>>teste;
    for(i=1; i<=teste; i++)
    {
        fin>>a>>b;
        Descompunere(b);
        fout<<a-Generare(a)<<"\n";
    }
}
int main()
{
    Ciur();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}