#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1 << 17, N = 1000004;
int nrprime;
unsigned char V[NMAX];
vector <int> p;


void ciur(){
    int i2;
    p.push_back(2);
    for (int i = 3; i <= N; i += 2) {
		if (V[i >> 4] & (1 << ((i >> 1) & 7))) continue;
		p.push_back(i);
		for (int j = i + (i2 = i + i); j <= N; j += i2)
			V[j >> 4] |= 1 << ((j >> 1) & 7);
	}
}

int main(){
    ciur();
    int teste;
    fin >> teste;
    int s_p = p.size();
    while (teste--){
        long long A, B;
        fin >> A >> B;
        vector <long long> factori;
        for (int i = 0; i < s_p && 1LL * p[i] * p[i] <= B; ++i){
            if (B % p[i] == 0){
                factori.push_back(p[i]);
                while (B % p[i] == 0){
                    B /= p[i];
                }
            }
        }
        if (B > 1){
            factori.push_back(B);
        }
        int s_factori = factori.size();
        int limit = (1 << s_factori) - 1;
        long long ans = 0;
        for (int mask = 0; mask <= limit; ++mask){
            long long val = 1;
            int contor = 0;
            for (int i = 0; i < s_factori; ++i){
                if (((mask >> i) & 1) == 1){
                    ++contor;
                    val = 1LL * val * factori[i];
                }
            }
            if (contor > 0){
                if (contor % 2 == 1){
                    ans += A / val;
                }
                else{
                    ans -= A / val;
                }
            }
        }
        ans = A - ans;
        fout << ans << "\n";
    }
}