#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int v[1000001],prime[80000],diviz[300],g[300];
int i,j,k,n,d,nr;
long long a,b,aux,total;
int main(){
    for(i=2;i<1000000;i++)
        if(v[i]==0){
            for(j=i+i;j<1000000;j+=i)
                v[j]=1;
            prime[++k]=i;
        }
    fin>>n;
    for(;n--;){
        fin>>a>>b;
        i=total=0;
        for(d=1;d<=k && b!=1 && prime[d]<=b/prime[d];d++)
            if(b%prime[d]==0){
                diviz[++i]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
        }
        if(b>1)diviz[++i]=b;

        for(j=0;j<300;j++)
            g[j]=0;

        while(!g[0]){
            j=i;
            while(j && g[j]==1){
                g[j]=0;
                j--;
            }
            if(j<1)break;
            g[j]=1;
            aux=1;
            nr=0;
            for(;j;j--)
                if(g[j]==1){
                    nr++;
                    aux*=diviz[j];
                }
            if(nr%2)
                total+=a/aux;
            else total-=a/aux;
        }
        fout<<a-total<<"\n";
    }
}