#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int NMAX=1000000;
bool ciur[NMAX+5];
long long prime [2*NMAX+10];
int main(){
    long long v[15],l,A,B,M,nr,p,sol,n=0;
    fin>>M;
    for (int i=2;i<=NMAX;i++){
        if (!ciur[i]){
            prime[++n]=i;
            for (int j=i*i;j<=NMAX;j+=i)
                ciur[j]=1;
        }
    }
    for(int k=1;k<=M;k++){
        fin>>A>>B;
        l=0, sol=0;
        if(B%2==0){
            v[++l]=2;
            while(B%2==0){
                B/=2;
            }
            for(int i=1;prime[i]*prime[i]<=B;i++){
                if(B%prime[i]==0){
                    v[++l]=prime[i];
                    while(B%prime[i]==0){
                        B/=prime[i];
                    }
                }
            }
            if(B>1){
                v[++l]=B;
            }
            for(int i=1;i<(1<<l);i++){
                nr=0;
                p=1;
                for(int j=0;j<l;j++){
                    if (i&(1<<j)){
                        nr++;
                        p=p*v[j+1];
                    }
                }
                if(nr&1){
                    sol+=A/p;
                }else{
                    sol-=A/p;
                }
            }
            fout<<A-sol<<'\n';
        }
    }
}