#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long d,t,i,T,k,n,a,nr,p,j,sol,b,v[1010],prime[1000010],x;
bool ciur[1000011];
void ciur1()
{
    for(d=2; d<=1000001; d++)
    {
        if(ciur[d]==0)
        {
            prime[++t]=d;
            for(i=d*d; i<=1000001; i=i+d)ciur[i]=1;
        }
    }
}
int main()
{
    ciur1();
    fin>>T;
    for(k=1; k<=T; k++)
    {
        fin>>a>>b;
        n=0;
        t=1;
        sol=0;
        while(prime[t]*prime[t]<=b)
        {
            if(b%prime[t]==0)
            {
                v[++n]=prime[t];
                while(b%prime[t]==0)b/=prime[t];
            }
            t++;
        }
        if(b!=1)v[++n]=b;
        x=1<<n;
        for(i=1; i<x; i++)
        {
            nr=0;
            p=1;
            for(j=0; j<n; j++)
            {
                if((i&(1<<j))!=0)
                {
                    nr++;
                    p=p*v[j+1];
                }
            }
            if(nr%2==1)sol+=a/p;
            else sol-=a/p;
        }
        fout<<a-sol<<'\n';
    }
    return 0;
}