#include <fstream>
#include <vector>
#include <bitset>
#define pb push_back
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
typedef long long ll;

ll a,b,cntbit[(1<<17)];
vector <ll> prime, divi;

void sieve();

int main(){
    int q;
    sieve();
    fin>>q;
    while(q--){
        ll sol=0,amm;
        fin>>a>>b;
        divi.clear();
        for(int i=0;i<prime.size() && prime[i]*prime[i] <= b;++i){
            if(b%prime[i] == 0){
                while(b%prime[i] == 0)
                    b/=prime[i];
                divi.pb(prime[i]);
            }
        }
        if(b>1) divi.pb(b);
        for(int msk=1;msk < (1<<divi.size());++msk){
            cntbit[msk]=cntbit[(msk-1)&msk]+1;
            amm=1;
            for(int i=0;i<divi.size();++i)
                if((1<<i)&msk)
                    amm*=divi[i];

            amm=a/amm;
            sol+=(cntbit[msk]%2 ? amm:-amm);
        }
        fout<<a-sol<<'\n';
    }
    return 0;
}
void sieve(){//all prime numbers up to 1e6
    bitset <(int)(1e6)> used;
    used.reset();
    prime.pb(2);
    for(int i=3;i<1e3;i+=2)
        if(!used[i]){
            used[i]=1;
            prime.pb(i);
            for(int j=i*i;j<1e6;j+=i)
                used[j]=1;
        }
    for(int i=1e3+1;i<1e6;i+=2)
        if(!used[i])
            prime.pb(i);
}