#include <fstream>
#include <cstring>

#define maxP 1000001
#define maxD 62501
#define maxNP 78499
#define maxDB 20

using namespace std;

ifstream in;
ofstream out;

char p[maxD];
int np[maxNP];
int d[maxDB];

int main()
{
    int M,B;
    long long A;

    in.open("pinex.in");

    in>>M;

    memset(p,0,sizeof(p));
    memset(np,0,sizeof(np));

    for(int i=1;((i*i)<<2)+(i<<2)+1<=maxP;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            for(int j=((i*i)<<1)+(i<<1);(j<<1)+1<=maxP;j+=(i<<1)+1)
                p[j>>3]|=(1<<(j&7));

    np[++np[0]]=2;
    for(int i=1;(i<<1)+1<=maxP;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            np[++np[0]]=(i<<1)+1;

    out.open("pinex.out");

    for(;M--;)
    {
        in>>A>>B;

        memset(d,0,sizeof(d));
        for(int i=1;i<=np[0]&&B!=1;++i)
            if(B%np[i]==0)
            {
                d[++d[0]]=np[i];
                while(B%np[i]==0) B/=np[i];
            }
        if(B!=1) d[++d[0]]=B;

        int powB=(1<<d[0]);
        long long sol=A;
        for(int i=1;i<powB;++i)
        {
            long long p=1;
            int b=0;
            for(int cnt=1,j=i;j;j>>=1,++cnt)
                if(j&1) p*=d[cnt],++b;

            if(b&1) p*=-1;
            sol+=A/p;
        }

        out<<sol<<'\n';
    }

    in.close();
    out.close();

    return 0;
}