#include <fstream>
#include <vector>
#define RADB 1000005
#define MAXX 30
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

int m,semn,x,j,comb[MAXX];
long long a,b,S,p;
bool ciur[RADB];
vector<int> prime,divb;

bool next_comb();

int main()
{
    int i,k;
    prime.push_back(2);
    for(i=3;i<=RADB;i+=2){
        if(!ciur[i]){
            ciur[i]=1;
            prime.push_back(i);
            for(j=i;j<=RADB;j+=2*i)
                ciur[j]=1;}}
    f>>m;
    for(i=1;i<=m;i++){
        f>>a>>b;
        S=0;
        divb.clear();
        for(j=0;j<prime.size()&&b>1;j++){
            if(!(b%prime[j])){
                x=prime[j];
                divb.push_back(x);
                while(!(b%x))
                    b/=x;}}
        if(b>1)
            divb.push_back(b);
        semn=-1;
        for(j=1;j<=divb.size();j++){
            p=1;
            semn*=(-1);
            for(k=1;k<=j&&p<=a;k++){
                comb[k]=k;
                p*=divb[k-1];}
            if(p>a)
                break;
            S+=(a/p)*semn;
            while(next_comb())
                S+=(a/p)*semn;}
        g<<a-S<<'\n';}
    f.close();
    g.close();
    return 0;
}

bool next_comb(){
    int i;
    if(comb[j]<divb.size()){
        p/=divb[comb[j]-1];
        comb[j]++;
        p*=divb[comb[j]-1];}
    else{
        for(i=j;i>=1&&comb[i]==divb.size()-j+i;i--);
        if(!i)
            return 0;
        p/=divb[comb[i]-1];
        comb[i]++;
        p*=divb[comb[i]-1];
        for(++i;i<=j;i++){
            p/=divb[comb[i]-1];
            comb[i]=comb[i-1]+1;
            p*=divb[comb[i]-1];}}
    return 1;}