#include<cstdio>
#include<vector>
using namespace std;
vector <long long> v;
char ciur[1000001];
vector <int> prime;
int main(){
    long long a,b,d,cb,nr,sol,prod;
    int m,i,ci,ind,num,j;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    for(d=2;d*d<=1000000;d++)
        if(ciur[d]==0)
            for(i=d*d;i<=1000000;i+=d)
                ciur[i]=1;
    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)
            prime.push_back(i);
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%lld%lld",&a,&b);
        j=0;
        cb=b;
        while(prime[j]*prime[j]<=cb){
            if(cb%prime[j]==0){
                v.push_back(prime[j]);
                while(cb%prime[j]==0)
                    cb/=prime[j];
            }
            j++;
        }
        if(cb!=1)
            v.push_back(cb);
        nr=(1<<v.size())-1;
        sol=0;
        for(j=1;j<=nr;j++){
            ci=j;
            ind=v.size()-1;
            prod=1;
            num=0;
            while(ind>=0){
                if(ci%2==1){
                    prod*=v[ind];
                    num++;
                }
                ci/=2;
                ind--;
            }
            if(num%2==1)
                sol+=a/prod;
            else
                sol-=a/prod;
        }
        printf("%lld\n",a-sol);
        v.clear();
    }
    return 0;
}