#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long prime[80000],diviz[20],g[20],i,j,k,n,d,nr,a,b,aux,total;
bitset<1000000> v;
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; prime[d]<=b/prime[d] && d<=k; d++)
            if(b%prime[d]==0){
                diviz[++i]=prime[d];
                while(b%prime[d]==0)
                    b/=prime[d];
            }
        if(b>1)diviz[++i]=b;

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