#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';
}

int bck(int index,int indDiv,int prod){
    int ans=0;
    for(int i=indDiv+1;i<diviz.size();++i){
        prod*=diviz[i];
        if(index>=2 && index<diviz.size())
            ans-=a/prod;
        if(index==diviz.size()){
            if((index-1)%2) ans-=a/prod;
            else ans+=a/prod;
        }
        ans+=bck(index+1,i,prod);
        prod/=diviz[i];
    }
    return ans;
}

void getAns(){
    int part=a;
    //int part = a-bck(0,-1,1);
    for(int i=0;i<diviz.size();++i)
        part+=bck(2,i,diviz[i]);
    fout<<part<<'\n';
    //if(diviz.size()!=1) for(auto i:diviz) part+=a/i;
}

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