#include <bits/stdc++.h>
using namespace std;

#define zero(x) (x & (-x))
#define ll long long

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

const int  MAXN = 1e6 + 3;
bool ciur[MAXN];
int v[MAXN], l = 0;
vector <int> divi;

void efect_ciur(){
    for(int i = 2; i < MAXN; ++i){
        for(ll j = 1LL*i * i ; j < MAXN; j += i)
            ciur[j] = 1;
        if(ciur[i] == 0) divi.push_back(i);
    }
}

void divizori(ll b){
    for(auto x: divi){
        if(1LL * x * x > b) break;
        if(b % x == 0) v[++l] = x;
        while(b % x == 0) b /= x;
    }
    if(b > 1) v[++l] = b;
}

void pinex(ll a){
    ll sol = a;
    for(ll i = 1; i < (1LL << l) ; ++i){
        ll sgn = 1, prod = 1;
        for(ll j = 0; j < l; ++j){
            if(i & (1LL << j)){
                sgn *= -1;
                prod *= v[j + 1];
            }
        }
        sol = sol + 1LL * a / prod * sgn;
    }
    l = 0;
    fout << sol << '\n';
}


int main(){
    int t ; fin >> t;
    efect_ciur();
    for(int i = 1; i <= t; ++i){
        ll a, b;
        fin >> a >> b;
        divizori(b);
        pinex(a);
    }
    return 0;
}
//8
//7
//14