#include <fstream>
#include <iostream>
#include <bitset>
using namespace std;

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

long long n,a,b,i,j,k,prim[300001],d,v[301],sol,cnt;
bitset <1000001> p;
bitset <301> w;

int main(){
    p[0]=1; p[1]=1;
    for(i=2;i<=1000000;i++)
        if(!p[i]){
            prim[++k]=i;

            for(j=2*i;j<=1000000;j+=i)
                p[j]=1;
        }

    fin>>n;
    for(;n;n--){
        fin>>a>>b;

        d=0;
        for(i=1;prim[i]*prim[i]<=b && i<=k && b!=1;i++){
            if(b%prim[i]==0){
                v[++d]=prim[i];
                //cout<<prim[i]<<" ";
                while(b%prim[i]==0)
                    b/=prim[i];
            }
        }
        if(b!=0){
            v[++d]=b;
            //cout<<b;
        }
        //cout<<"\n";

        sol=0;
        w.reset();
        while(w[d+1]==0){
            i=1;
            while(w[i]==1)
                w[i++]=0;
            w[i]=1;

            if(i==d+1)
                break;

            cnt=0; j=1;
            for(i=1;i<=d;i++)
                if(w[i]){
                    j*=v[i];
                    cnt++;
                }

            if(cnt%2==1)
                sol+=a/j;
            else
                sol-=a/j;
        }

        fout<<a-sol<<"\n";
    }


    return 0;
}