#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

vector<int> succesor;
vector<int> divizori;


int main()
{

long long int a,b,i,j,k,m,n,t,nr,nr_fin,factor;
fin>>t;
while(t--)
{
    fin>>a>>b;
    divizori.push_back(1);
    nr_fin=0;
    for(i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            divizori.push_back(i);
            do{
                b/=i;
            }
            while(b%i==0);
        }
    }
    if(b!=1)
        divizori.push_back(b);
    for(i=0;i<divizori.size();i++)
        succesor.push_back(0);

    while(succesor[0]==0)
    {
        factor=1;
        nr=0;
        for(i=1;i<succesor.size();i++)
            if(succesor[i])
                {
                    factor*=divizori[i];
                    nr++;
                }

        if(nr%2)
            nr_fin-=a/factor;
        else
            nr_fin+=a/factor;

        for(i=succesor.size()-1;i>-1 && succesor[i]==1;i--)
            succesor[i]=0;
        succesor[i]=1;

    }
    fout<<nr_fin<<'\n';
    divizori.clear();
    succesor.clear();
}

    return 0;
}