#include<fstream>
#define MAX 1000000
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
int s,sum,k,t,a,b,n,m,poz,d[30],v[30],p[1000001];
bool aa[MAX +5];
void ciur()
{
    poz=0;
    for(int i=2; i<=MAX; ++i)
    {
        if(!aa[i])
        {
            p[++poz]=i;
            for(int j=i+i; j<=MAX; j+=i)
                aa[j]=1;
        }
    }
}
void prelsol()
{
    int i;
    long long pr=1;
    for(i=1; i<=n; i++) pr=pr*d[v[i]];
    s+=a/pr;
}
void back()
{
    k=1,v[k]=0,s=0;
    do
    {
        while(v[k]<m-n+k)
        {
            v[k]++;
            if(k==n) prelsol();
            else
            {
                k++;
                v[k]=v[k-1];
            }
        }
        k--;
    }
    while(k);
    if(n%2) sum+=s;
    else sum-=s;
}
int main()
{
    ciur();
    in>>t;
    while(t--)
    {
        in>>a>>b;
        m=0;
        int i=1;
        while(b>1 && p[i]*p[i]<=b)
        {
            if(b%p[i]==0)
            {
                d[++m]=p[i];
                while(b%p[i]==0) b/=p[i];
            };
            i++;
        }
        if(b>1) d[++m]=b;
        sum=0;
        for(n=1; n<=m; n++) back();
        out<<a-sum<<'\n';
    }
    out.close();
    return 0;
}