#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;
    for(ull i=2;i*i<DM;++i) if(!isNP[i]){
        pr.pb(i);
        for(ull j=i*i;j<DM;j+=i) isNP[j]=1;
    }
}

void _search(int x){
    diviz.clear();
    for(auto i:pr) if(!(x%i))
        diviz.pb(i);
}

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

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

    for(int i=1;i<(1<<(diviz.size()));++i){
        int cnt=0,prod=1;
        for(int j=0;(1<<j)<=i;++j)
            if((1<<j)&i) cnt++,prod*=diviz[j];
        if(cnt%2) part-=a/prod;
        else part+=a/prod;
    }

    fout<<part<<'\n';
}

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