#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool v[1000001];
int prime[100000];
int  diviz[300];
int g[300];
int i,j,k,n,d,nr,t;
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=0;
        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<=i+1;j++)
            g[j]=0;
        while(!g[0]){
            j=i;
            while(g[j]==1){
                g[j]=0;
                j--;
            }
            if(j<1)break;
            g[j]=1;
            aux=1;
            nr=0;
            for(t=j;t;t--)
                if(g[t]==1){
                    nr++;
                    aux*=diviz[t];
                }
            if(nr%2)
                total+=a/aux;
            else total-=a/aux;
        }
        fout<<a-total<<"\n";
    }
}