#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

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

void solve();

int main()
{   
    int T; fin >> T;
    while (T--)
        solve();

    return 0;
}

void solve(){
    ll a, b; fin >> a >> b;
    vector<ll> d;
    if (b % 2 == 0){
        while (b % 2 == 0)  
            b /= 2;
        d.pb(2);
    }
    int i = 3;
    for (; i * i <= b; i+=2) 
        if (b % i == 0){
            d.pb(i);
            while (b % i == 0) 
                b /= i;
        }
    if (b != 1) d.pb(b);

    int k = d.size(); ll msk = (1<<k);
    ll r = 0;
    for (ll i = 1; i < msk; i++){
        ll nr = -1; 
        for (int u = 0; u < k; u++)
            if (i & (1<<u)) nr *= -d[u];
        
        r += a / nr;
    }
    fout << a - r << '\n';

}