#include <iostream>
#include <cstdio>

using namespace std;

char ciur[1000001];
int prime[80000];
long long divi[20];
int main(){
    FILE *fin, *fout;
    int i,j,pun,M,k,d,nr;
    long long sol,A,B,p;
    fin=fopen("pinex.in","r");
    fout=fopen("pinex.out","w");
    fscanf(fin,"%d",&M);
    for(i=2;i*i<=1000000;i++)
        if(ciur[i]==0){
            for(j=i*i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    pun=0;
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
            prime[++pun]=i;
    while(M){
        fscanf(fin,"%lld %lld\n",&A,&B);
        k=0;
        pun=1;
        d=prime[pun];
        while(d*d<=B && B>1){
            if(B%d==0){
                divi[++k]=d;
                while(B%d==0)
                    B/=d;
            }
            d=prime[++pun];
        }
        if(B>1)
            divi[++k]=B;
        sol=0;
        for(i=1;i<(1<<k);i++){
            p=1;
            nr=0;
            for(j=0;j<k;j++)
                if((1<<j)&i){
                    p=1LL*p*divi[j+1];
                    nr++;
                }
            if(nr%2==0)
                nr=-1;
            else
                nr=1;
            sol=sol+1LL*nr*(A/p);
        }
        sol=A-sol;
        fprintf(fout,"%lld\n",sol);
        M--;
    }
    fclose(fin);
    fclose(fout);
    return 0;
}