#include <fstream>
//#include <iostream>
using namespace std;
long long unsigned int nr, s=0, v[5000], a;
bool prime [100005];
void gen ()
{
    int i, j;
    for (i = 2; i <= 100000; ++i)
        prime[i] = 1;
    for (i = 2; i <= 100000; ++i)
        if (prime[i])
        {
            //nr++;
            for (j = i+i; j <= 100000; j += i)
                prime[j] = 0;
        }
}
long long unsigned int isprim(long long unsigned int k)
{
    if((k%2==0) && (k!=2))
        return 0;
        for(int i=3;i*i<=k;i=i+2)
            if(k%i==0)
                return 0;
    return 1;
}
long long unsigned int factprimi ( long long unsigned int b)
{
    long long unsigned int i=2;
    nr=0;
    while(i<=100000)
    {
        if(prime[i])
        {
            if(b%i==0)
            {
                b=b/i;
                v[nr]=i;
                ++nr;
                ++i;
                //cout<<n<<" ";
            }
            else i++;
        }
        else i++;
    }
    if(b>100000)
        if(isprim(b))
        {
            v[nr]=b;
            b=1;
            nr++;
        }
    return b;
}
long long unsigned int pinex()
{
    long long int sol=0, i, j, p, n;
        for (i=1;i<(1<<nr);i++)
        {
            p=1;
            n=0;
            for(j=0;j<nr;j++)
                if((1<<j) & i)
                {
                p*=v[j];
                n++;
                }
            if(n%2==1)
                n=1;
            else n=-1;
            sol+=n*(a/p);
        }
    return sol;
}
int main()
{
    long long unsigned int m, i, b, b1, r, j, d, sol;
    ifstream in ("pinex.in");
    ofstream out ("pinex.out");
    gen ();
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        b1=factprimi(b);
        sol=pinex();
        out<<a-sol<<"\n";

    }
    return 0;
    ///principiu lu peste
}