#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
const int MAXP=1000000;
int M,lp=0,lg=0;
long long int A,B,p[33],prim[MAXP/2],nrsol;
bool b[MAXP];
int main()
{
    b[2]=0;
    prim[++lp]=2;
    for(int i=4; i<MAXP; i+=2)
        b[i]=1;
    for(int i=3; i*i<MAXP; i+=2)
        if(b[i]==0)
        {
            prim[++lp]=i;
            for(int j=i*i; j<MAXP; j+=i)
                 b[j]=1;
        }
    f>>M;
    while(M--)
    {
        f>>A>>B;
        int j=1;
        lg=0;
        while(B>1)
        {
            if(B%prim[j]==0)
            {
                while(B%prim[j]==0) B/=prim[j];
                p[++lg]=prim[j];
            }
            j++;
        }
        if(lg==0) p[++lg]=B;
        int nt=1<<lg;
        long long int card=0;
        for(int i=1; i<nt; i++)
        {
            long long int t=A;
            int j=0,p2,ndiv=0;
            while((p2=1<<j)<=i)
            {
                if(p2&i)
                {
                    t/=p[j+1];
                    ndiv++;
                }
                j++;
            }
            if(ndiv%2==0)
                card-=t;
            else
                card+=t;

        }
        nrsol=A-card;
        g<<nrsol<<'\n';
    }
    return 0;
}