#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

#define nmax 31
#define Ciurmax 100002
#define ll long long

ifstream f("pinex.in");
ofstream g("pinex.out");

int viz[Ciurmax];
vector<int> prim, divPrim;

void bagaCiur(){
    for(int i=2; i<Ciurmax; ++i){
        if (viz[i] == 0){
            prim.push_back(i);
            for(int j=i*2; j<Ciurmax; j+=i){
                viz[j] = 1;
            }
        }
    }
}

void divizoriPrimi(ll B){
    int i=0; divPrim.clear();
    while(i<prim.size() && prim[i]*prim[i] <= B){
        if (B % prim[i] == 0){
            while( B % prim[i] == 0){
                B = B / prim[i];
            }
            divPrim.push_back(prim[i]);
        }
        ++i;
    }
    if (B > 1) divPrim.push_back(B);
}

inline int bagaPinex(ll A, ll B){
    divizoriPrimi(B);
    //for(int i=0; i<divPrim.size(); ++i) cout << divPrim[i] << " ";
    //cout << "\n";

    int lim = (1<<divPrim.size());
    int Cnt = 0; // avand in vedere ca divizorii lui B sunt numere prim  => sunt prime intre ele
    // => cmmdc(di, dk) == 1 => cmmmc(di,dk) = di*dk;
    for(int conf=1; conf<lim; ++conf){
        int Cmmmc = 1; int cnt1 = 0;// imi zice cati bati de 1 are conf
        for(int i=0; i<divPrim.size(); ++i){
            if ( ( conf & (1<<i) ) != 0 ){// e bit de 1
                cnt1++; Cmmmc = Cmmmc * divPrim[i];
            }
        }
        int Cati = A / Cmmmc;// imi zice cate numere sunt in intervalul 1...A care sunt divizibile
        // cu divizorii din Conf
        if (cnt1 % 2 == 0){// trebuie scazute
            Cnt -= Cati;
        }else Cnt += Cati;
    }
    return A-Cnt;
}

void rezolva(){
    // ideea ar fi ca numelre neprime cu B <= A le-as putea afla direct doar prin brut
    // dar le-as mai putea afla si asa : aflu numarele <= A dar neprime cu B;
    // adica fiecare numar de la 1... A care e divizor a lui B sau il divide pe B
    // => un astfel de numar o sa il divida pe un divizor prim de a lui B;
    // => fie d1, d2, d3 .. divizorii primi a lui B => A1 = d1, d1*2, d1*3, ... d1*K a. i. d1*K <= A
    // A2 = d2*1, d2*2...
    // ma intereseaza reuniune acestor multimii
    int t = 0; f>>t;
    ll A, B;
    bagaCiur();
    for(; t; --t){
        f >> A >> B;
        g << bagaPinex(A, B) << "\n";
    }
}

int main(){
    rezolva();

    f.close();
    g.close();

    return 0;
}