#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
#define ll long long
int dprim[100];
//int sol[100];
ll rez, prod, nr;
ll a, b;
void bt(int p, int k){
    int i;
    if(p > k){
        /*ll prod = 1;
        int nr = 0;
        for(i = 1; i <= k; i++)
            if(sol[i] == 1){
                prod *= dprim[i];
                nr++;
            }
        if(nr % 2 == 0)
            nr = -1;
        else
            nr = 1;
        rez = rez + nr * prod;*/
        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++){
            //sol[p] = 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;
    d = 2;
    k = 0;
    while( b > 1){
        if( b % d == 0){
            dprim[++k] = d;
            while(b % d == 0){
                b /= d;
            }
        }
        if(d == 2)
            d++;
        else
            d += 2;
    }
    rez = 0;
    nr =0;
    prod = 1;
    bt(1,k);
    return a - rez;
}

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