#include <fstream>
#include <math.h>
#include <vector>

using namespace std;

#define MAXPR 1000000

long long m, a, b, fact[30];
bool ciur[MAXPR];
vector<int> prim;

void prec(){
    for(int i = 2; i < MAXPR; i++)
        if(!ciur[i]){
            prim.push_back(i);
            for(int j = 2 * i; j < MAXPR; j += i)
                ciur[j] = 1;
        }
}

int main() {

    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    prec();
    fin >> m;
    for(int i = 1; i <= m; i++) {
        fin >> a >> b;
        long long t = 0, d = 0;
        while(b > 1){
            if(b % prim[d] == 0){
                fact[++t] = prim[d];
                while (b % prim[d] == 0)
                    b /= prim[d];
            }
            if(prim[d] > sqrt(b) && b > 1){
                fact[++t] = b;
                b = 1;
            }
            d++;
        }
        long long sol = a;
        for(int i = 1; i < (1 << t); i++){
            long long nr = 0, prod = 1;
            for(int j = 0; j < t; j++)
                if((1 << j) & i) {
                    prod *= 1LL * fact[j + 1];
                    nr++;
                }
            if(nr % 2) nr = -1;
            else nr = 1;
            sol += nr * a / prod;
        }
        fout << sol << "\n";
    }
    return 0;
}