#include <fstream>
#include <vector>
#define VAL 1000005
#define DIV 25
#define LL long long

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int T, i, j, K, cnt, nr;
LL d[DIV], A, B, ans, P;
vector<LL> prim;
vector<LL> :: iterator it;
bool ok[VAL];

void Sieve()
{
    LL i, j;
    for (i=2; i<VAL; i++)
    {
        if (ok[i]==false)
        {
            prim.push_back(i);
            for (j=i*i; j<VAL; j+=i)
              ok[j]=true;
        }
    }
}

int main()
{
    fin >> T;
    Sieve();
    for (cnt=1; cnt<=T; cnt++)
    {
        fin >> A >> B;
        K=ans=0;
        for (it=prim.begin(); it!=prim.end() && (*it)*(*it)<=B ; it++)
        {
            if (B % (*it)==0)
            {
                d[K]=*it;
                while (B % (*it)==0)
                  B/=*it;
                K++;
            }
            if (B==1)
              break;
        }
        if (B!=1)
          d[K++]=B;
        for (i=1; i<(1 << K); i++)
        {
            nr=0;
            P=1;
            for (j=0; j<K; j++)
            {
                if ((i & (1 << j))!=0)
                {
                    nr++;
                    P*=d[j];
                }
            }
            if (nr % 2==1)
              ans+=A / P;
            else
              ans-=A / P;
        }
        fout << A-ans << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}