#include <fstream>
#include <cstring>
#define DIM (1<<20)
using namespace std;

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

int N, M, i, j, K, Desc[DIM];
int Ciur[DIM], Prime[DIM], Fact[DIM];
int Back[DIM];
long long g, Q, prod, sum, nr, last;
long long A, B, t;

void Ciurerat(){
    Prime[++K] = 2;
    for(i = 3; i < DIM; i += 2)
        if(Ciur[i] == 0){
            for(j = i + i; j < DIM; j += i)
                Ciur[j] = 1;
            Prime[++K] = i;
        }
    return;
}

void Descompose(int val){
    g = 0;
    int valo = val;
    for(i = 1; Prime[i] * Prime[i] <= valo && val != 1; i ++){
        if(val % Prime[i] == 0){
            Desc[++g] = Prime[i];
            while(val % Prime[i] == 0)
                val /= Prime[i];
        }
    }
    if(val != 1)
        Desc[++g] = val;
    return;
}

void ProdCalc(){
    prod = 1;
    for(int i = 1; i <= g; i ++)
        if(Back[i] == 1)
            prod *= Desc[i];
    return;
}

void BackTracking(){
    sum = 0; nr = 0;
    Back[0] = 0;
    while(Back[0] == 0){
        last = g;
        while(Back[last] == 1){
            Back[last--] = 0;
            nr --;
        }
        nr ++;
        Back[last] = 1;
        if(Back[0] == 1)
            break;
        ProdCalc();
        if(nr % 2 == 1)
            sum += A / prod;
        else
            sum -= A / prod;
    }
    return;
}

void CodeExpert(){
    fin >> Q;
    for(t = 1; t <= Q; t ++){
        fin >> A >> B;
        //memset(Fact, 0, sizeof(Fact)
        Descompose(B);
        BackTracking();
        fout << A - sum << "\n";
    }
    return;
}

int main(){
    Ciurerat();
    CodeExpert();
    return 0;
}