#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e6;
bool ciur[NMAX+5];
int prime[80005];
long long v[15];
int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    ciur[0]=ciur[1]=1;
    for(int i=2;i*i<=NMAX;i++){
        if(ciur[i]==0){
            for(int j=i*i;j<=NMAX;j+=i){
                ciur[j]=1;
            }
        }
    }
    int p=0;
    for(int i=1;i<=NMAX;i++){
        if(ciur[i]==0){
            p++;prime[p]=i;
        }
    }
    int t;unsigned long long a,b;
    fin>>t;
    for(int test=1;test<=t;test++){
        fin>>a>>b;
        int poz=1,d=2,cnt=0,fact=0;
        while(b>1&&1ULL*d*d<=b){
            cnt=0;
            while(b%d==0){
                cnt++;b/=d;
            }
            if(cnt>0){
                fact++;v[fact]=d;
            }
            poz++;d=prime[poz];
        }
        if(b>1){
            fact++;v[fact]=b;
        }
        unsigned long long nr=0;
        int p2=(1<<fact);
        for(int i=1;i<p2;i++){
            int ci=i,acum=1,ok=0,biti=-1;unsigned long long prod=1;
            while(ci>0){
                if(ci&1){
                    prod*=v[acum];biti*=-1;
                }
                ci/=2;acum++;
            }
            if(ok==0){
                unsigned long long ceva=a/prod;
                nr+=1ULL*biti*ceva;
            }
        }
        unsigned long long rez=a-nr;
        fout<<a-nr<<'\n';
    }
    return 0;
}