#include <fstream>
using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

bool ciur[1000005];
int prime[1000005], nrdiv[15], nrp;

void formare_ciur(){
    for(int i = 4; i <= 1000000; i += 2){
        ciur[i] = 1;
    }
    for(int i = 3; i * i <= 1000000; i += 2){
        if(ciur[i] == 0){
            for(int j = 3 * i; j <= 1000000; j += 2 * i){
                ciur[j] = 1;
            }
        }
    }
    nrp = 0;
    for(int i = 2; i <= 1000000; i ++){
        if(ciur[i] == 0){
            prime[++ nrp] = i;
        }
    }
}

int desc(int n){
    int d, dp;
    d = 1;
    dp = 0;
    while(prime[d] * prime[d] <= n && n > 1){
        int e = 0;
        while(n % prime[d] == 0){
            n /= prime[d];
            e ++;
        }
        if(e > 0){
            nrdiv[++ dp] = prime[d];
        }
        d ++;
    }
    if(n > 1){
        nrdiv[++ dp] = n;
    }
    return dp;
}

int main(){
    int n, a, b;
    formare_ciur();
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a >> b;
        int r = 0;
        int nr = desc(b);
        int nr_bits = 0;
        long long product = 1;
        for(int j = 0; j < (1 << nr); j ++){
            product = 1;
            nr_bits = 0;
            for(int l = 0; l < nr; l ++){
                if(j & (1 << l)){
                    nr_bits ++;
                    product = 1LL * product * nrdiv[l + 1];
                }
            }
            if(product > 0){
                if(nr_bits % 2 == 0){
                    r = r + a / product;
                }
                else {
                    r = r - a / product;
                }
            }
        }
        cout << r << "\n";
    }
    return 0;
}