#include <bits/stdc++.h>
#define ll int64_t
using namespace std;
#if 1
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define cin fin
#define cout fout
#endif // 1
ll a,b;
const ll nmx = 1e6 + 3;
int era[nmx]; /// 1 - neprim
vector<ll> pr;
void calcEras(){
    for(ll i=4;i<nmx;i+=2)
        era[i] = 1;
    era[0] = era[1] = 1;
    for(ll i=3;i<nmx;i+=2)
        if(era[i] == 0)
            for(ll j=i*i;j<nmx;j+=i)
                era[j] = 1;
    for(ll i=0;i<nmx;i++)
        if(era[i] == 0){
            pr.push_back(i);
        }
}

vector<ll> dec(ll x){
    vector<ll> v;
    ll i = 0;
    while(pr[i]*pr[i]<=x){
        if(x%pr[i]==0){
            v.push_back(pr[i]);
            do
                x /= pr[i];
            while(x%pr[i]==0);
        }
        i++;
    }
    if(x!=1)
        v.push_back(x);
    return v;
}

void solve(){
    cin >> a >> b;
    auto divs = dec(b);
    ll ans = 0;
    for(ll msk=1;msk<(1<<divs.size());msk++){
        ll nr = 1,cnt = 0;
        for(ll j=0;j<divs.size();j++)
            if((1<<j)&msk)
                cnt++, nr*=divs[j];
        ans += (cnt&1 ? 1 : -1) * a / nr;
    }
    cout << a-ans << "\n";

}

int main()
{
    calcEras();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}