#include <bits/stdc++.h>
#define DM 1000005
#define ull unsigned long long
#define pb push_back
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

vector<ull>pr,diviz;
bitset<DM>isNP;
ull a,b,m;

void ciur(){
    isNP[0]=isNP[1]=1;
    ull i=2;
    for(;i*i<DM;++i) if(!isNP[i]){
        pr.pb(i);
        for(ull j=i*i;j<DM;j+=i) isNP[j]=1;
    }
    for(;i<DM;++i) if(!isNP[i])
        pr.pb(i);
}

void _search(ull x){
    diviz.clear();
    ull cop = x;
    for(auto i:pr){
        if(cop==1 || i*i>x)
            break;
        if(!(cop%i)){
            diviz.pb(i);
            while( !(cop%i) ) cop/=i;
        }
    }
    if(cop>1) diviz.pb(cop);
}

void afis(){
    for(auto i:diviz) fout<<i<<" ";
    fout<<'\n';
}

void getAns(){
    ull ans=a,prodPart=1;

    for(ull i=1;i<(1<<diviz.size());++i){
        ull cnt=0,prod=1;
        for(int j=0;(1<<j)<=i;++j)
            if( ((1<<j)&i) ) cnt++,prod*=diviz[j];
        if(cnt==0) continue;
        if(cnt%2) ans-=a/prod;
        else ans+=a/prod;
    }
    fout<<ans<<'\n';
}

int main()
{
    fin>>m;
    ciur();
    while(m--){
        fin>>a>>b;
        _search(b);
        getAns();
    }
    return 0;
}