#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int MAXN = 1e6 + 1;
bool ciur[MAXN];
vector <int> divi;
long long v[100], l;
void efect_ciur(){
    for(int i = 2; i < MAXN; ++i){
        for(long long j = 1LL*i * i; j < MAXN; j += i)
            ciur[j] = 1;
        if(ciur[i] == 0) divi.push_back(i);
    }
}
void divizori(long long b){
    for(auto x : divi) {
        if (1LL * x * x > b) continue;
        if(b % x == 0) v[++l] = x;
        while (b % x == 0) b /= x;
    }
    if (b > 1) v[++l] = b;
}
void efect_pinex(long long a){
    long long sol = a;
    for(long long i = 1; i < (1LL << l); ++i){
        long long sgn = 1, prod = 1;
        for(long long j = 0; j < l; ++j){
            if(i & (1LL << j)){
                sgn *=  (-1);
                prod *= v[j + 1];
                //cout << prod << " " << v[j + 1] << '\n';
            }
        }
        sol = sol + 1LL*a/prod * sgn;
    }
    l = 0;
    fout << sol << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);
    int t; fin >> t;
    efect_ciur();
    for(int i = 1; i <= t; ++i){
        long long a, b;
        fin >> a >> b;
        divizori(b);
        efect_pinex(a);
    }
    return 0;
}