#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

/// <---------------------------------

typedef long long ll;

/// <---------------------------------

const int LIM=1000000;
const int CNT=78498;

/// <---------------------------------

int pr[CNT+5],cnt=0;
int lp[LIM+5];

void build_prime(){
    for(int i=2;i<=LIM;i++) {
        if(lp[i]==0) {
            lp[i]=i;
            pr[++cnt]=i;
        }
        for(int j=1;j<=cnt && pr[j]<=lp[i] && i*pr[j]<=LIM;j++)
            lp[i*pr[j]]=pr[j];
    }
}

/// <--------------------------------

int y=0;
ll who[100];

void add(ll val) {
    y=0;
    int poz=1;
    while((ll)pr[poz]*pr[poz]<=val) {
        int cate=0;
        while(val%pr[poz]==0) {
            val/=pr[poz];
            cate++;
        }
        if(cate)
            who[++y]=pr[poz];
        poz++;
    }
    if(val>1)
        who[++y]=val;
}

/// <---------------------------------

ll val=0;
ll ans=0;

void bkt(int strat,int add,ll prod) {
    if(strat==y)
        ans+=add*(val/prod);
    else {
        bkt(strat+1,add,prod);
        bkt(strat+1,add*-1,prod*who[strat+1]);
    }
}

/// <---------------------------------


int main(){
    build_prime();
    int t;
    fin>>t;
    while(t--) {
        ans=0;
        fin>>val;
        ll b;
        fin>>b;
        add(b);
        bkt(0,1,1);
        fout<<ans<<"\n";
    }
    return 0;
}