#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<int> 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 == i * i) { d.pb(i); b = 1; }
    if (b != 1) d.pb(b);

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

}