#include <fstream>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
#define ll long long
ll dprim[100];
int fprim[80000];
bool prim[1000001];
ll rez, prod, nr;
ll a, b;
void ciur(){
    int i, j, k;
    for(i = 2; i * i <= 1000000; i++)
        if(!prim[i]){
            for(j = i * i; j <= 1000000; j += i)
                prim[j] = true;
        }
    k = 0;
    for(i = 2; i  <=  1000000; i++)
        if(!prim[i])
            fprim[++k] = i;
}
void bt(int p, int k){
    int i;
    if(p > k){
        int coef;
        if(nr > 0){
            if(nr % 2 == 0)
                coef = -1;
            else
                coef = 1;
            rez = rez + coef * a / prod;
        }
    }
    else{
        for(i = 0; i <= 1; i++){
            nr += i;
            if(i == 1)
                prod *= dprim[p];
            bt(p+1,k);
            nr -= i;
            if(i == 1)
                prod /= dprim[p];
        }
    }
}
ll rezolva(){
    int d, k;
    k = 0;
    d = 1;
    while(fprim[d] <= sqrt(b)){
        if(b % fprim[d] == 0){
            dprim[++k] = fprim[d];
            while(b % fprim[d] == 0)
                b /= fprim[d];
        }
        d++;
    }
    if(b > 1)
        dprim[++k] = b;

    rez = 0;
    nr =0;
    prod = 1;
    bt(1,k);
    return a - rez;
}

int main()
{
    int n, i;
    f >> n;
    ciur();
    for(i = 1; i <= n; i++){
        f >> a >> b;
        g << rezolva() << '\n';
    }
    return 0;
}