#include <fstream>

using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");
int E[1000001];
int M;
long long n,x;
long long rez;
int S[20];
long long F[21];
int k;
int nrp;
int P[200000];

void g(int kappa)
{
    int i,nr1;
    long long f;
    if (kappa==k)
    {
        nr1=0;
        for (int i=1;i<=kappa;i++)
            if (S[i]==1)
                nr1++;
        f=1;
        for (int i=1;i<=kappa;i++)
            if (S[i]==1)
                f=f*F[i];
        if (nr1%2==1)
            rez=rez+n/f;
        else
            if (nr1!=0)
                rez=rez-n/f;
    }
    else
        for (i=0;i<=1;i++)
        {
            S[kappa+1]=i;
            g(kappa+1);
        }
}
long long numar(long long n, long long x)
/// returneaza cate numere de la 1 la n sunt prime cu x
{
    long long cx;
    int d;
    cx=x;
    /// se descompune x in factori primi
    k=0;
    while (cx>1)
    {
        d=0;
        for (int i=1;i<=nrp;i++)
            if (cx%P[i]==0)
            {
                d=P[i];
                break;
            }
        if (d==0)
        {
            k++;
            F[k]=cx;
            break;
        }
        else
        {
            k++;
            F[k]=d;
            while (cx%d==0)
                cx=cx/d;
        }
    }
    /// backtracking pentru a genera toate sirurile de lungime k
    /// cu valori posibile 0 sau 1
    rez=0;
    g(0);
    return n-rez;
}

int main()
{
    for (int i=2;i<=1000000;i++)
        E[i]=1;
    for (int i=2;i<=1000000;i++)
        if (E[i]==1)
            for (int j=i+i;j<=1000000;j=j+i)
                E[j]=0;
    nrp=0;
    for (int i=2;i<=1000000;i++)
        if (E[i]==1)
            P[++nrp]=i;
    fi>>M;
    for (int i=1;i<=M;i++)
    {
        fi>>n>>x;
        fo<<numar(n,x)<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}