#include <fstream>
#include <string>
#include <unordered_map>
#include <set>
using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long t,a,b,k,p;
long long sol,prime[100005],f[105],x[105],pr;
bool ciur[1000005];
void back(int pas)
{
    for(int i=x[pas-1]+1; i<=k; i++)
    {
        x[pas]=i;
        pr*=f[i];
        back(pas+1);
        if(pas%2==1)
            sol+=a/pr;
        else
            sol-=a/pr;
        pr/=f[i];
    }
}
int main()
{

    ciur[0]=1;
    ciur[1]=1;
    for(int i=2; i<=1000000; i++)
        if(ciur[i]==0)
        {
            prime[++p]=i;
            for(int j=2*i; j<=1000000; j+=i)
                ciur[j]=1;
        }
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        k=0;
        for(int i=1; i<=p&&1ll*prime[i]*prime[i]<=b; i++)
            if(b%prime[i]==0)
            {
                f[++k]=prime[i];
                while(b%prime[i]==0)
                    b/=prime[i];
            }
        if(b!=1)
            f[++k]=b;

        sol=0;
        pr=1;
        back(1);
        cout<<a-sol<<'\n';
    }
    return 0;
}
///nr de elemente <=a si prime cu b