#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int NM = 1000005;
typedef long long ll;

ifstream in("pinex.in");
ofstream out("pinex.out");

vector<ll> prime;
vector<ll> divB;
int eprim[NM];

void ciur(){
    for(int i=2;i<NM;++i)
        eprim[i]=1;
    for(int i=2;i<NM;++i){
        if(eprim[i]){
            prime.pb(i);
            for(int j=i+i;j<NM;j+=i)
                eprim[j]=0;
        }
    }

}


ll solve(ll A,ll B){
    divB.clear();
    for(auto e:prime)
        if(B%e==0)
            divB.pb(e);
    ll n=divB.size();
    ll semn=1;
    ll val=1;
    ll sol=A;
    for(int mask=1;mask<(1<<n);++mask){
        val=1;
        semn=1;
        for(int i=0;i<n;++i){
            if(mask&(1<<i)){
                val=val*divB[i];
                semn=semn*(-1);
            }
        }
       sol=sol+semn*(A/val);
    }
    return sol;
}

int main()
{
    ciur();
    int t;
    ll x,y;
    in>>t;
    while(t--){
        in>>x>>y;
        out<<solve(x,y)<<'\n';
    }
    return 0;
}