#include <fstream>
#include <vector>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
bool ciur[1000001];
vector<long long>nrprime, divB;
int main()
{
    for(int i=4; i<=1000000; i+=2)
        ciur[i]=1;
    for(int i=3; i<1000; i+=2)
    {
        if(ciur[i]==0)
            for(int j=i*i; j<=1000000; j+=i)
                ciur[j]=1;
    }
    for(int i=2; i<=1000000; i++)
        if(ciur[i]==0)
            nrprime.push_back(i);
    long long q,a,b;
    cin>>q;
    while(q>0)
    {
        while(!divB.empty())
            divB.pop_back();
        cin>>a>>b;
        int poz=0;
        while(poz<nrprime.size() && nrprime[poz]<=b)
        {
            if(b%nrprime[poz]==0)
            {
                divB.push_back(nrprime[poz]);
                while(b%nrprime[poz]==0)
                    b/=nrprime[poz];
            }
            if(nrprime[poz]*nrprime[poz]>b)
            {
                divB.push_back(b);
                break;
            }
            poz++;
        }

        long long nrdivizori=divB.size();
        long long rasp=0;
        for(int i=0; i<(1<<nrdivizori); i++) ///i descompus in baza 2 va fi o serie de 1 si 0, unde 1 pe pozitia k inseamna ca i il contine pe pk in descompunerea in factori primi
        {
            int nrprime_in_desc=0;
            long long numar=1;
            for(int j=0; j<nrdivizori; j++)
            {
                if(i & (1<<j))
                    numar*=divB[j], nrprime_in_desc++;
            }
            if(nrprime_in_desc%2==1)
                rasp-=a/numar;
            else
                rasp+=a/numar;
               // cout<<rasp<<'\n';
        }
        cout<<rasp<<'\n';
        q--;
    }
    return 0;
}
/*
pentru un numar b avand p1, p2, ...,pk div primi
rasp este:
a/p1 + a/p2 + ... +a/pk
-a/p1p2 - a/p1p3 - .... -a/(pk-1)pk
+a/p1p2p3 + ...
-a/p1p2p3p4 - ...
etc
*/