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

const int sqm = 1000000;

int m;

long long a,b;


bool ciur[sqm + 5];

vector <int> dvz;

int nr[16];
int bk[16];

void prim()
{
    ciur[0]=1;
    ciur[1]=1;
    for(int i=2; i<=sqm; i++)
        if(!ciur[i])
        {
            dvz.push_back(i);
            for(int j= 2*i; j<=sqm; j+=i)
                ciur[j]=true;
        }
}
void backt(int pas,long long& sol,long long prod = 1)
{
    if(prod!=1)
    {
        if(pas%2)
            sol+=a/prod;
        else
            sol-=a/prod;
    }
    if(pas==nr[0]+1)
        return;
    for(int i = bk[pas-1]+1; i<=nr[0]; i++)
    {
        bk[pas]=i;
        backt(pas+1,sol,prod*nr[bk[pas]]);
    }
}
void solve()
{
    nr[0]=0;
    fin>>a>>b;
    for(auto& i : dvz)
    {
        if(i*i>b)
            break;
        if(b%i==0)
        {
            while(b%i==0)
                b/=i;
            nr[++nr[0]]=i;
        }
    }
    if(b!=1)
        nr[++nr[0]]=b;
    long long sol = a;
    backt(1,sol);
    fout<<sol<<'\n';
}

int main()
{
    prim();
    fin>>m;
    for(int i=1; i<=m; i++)
        solve();
}