#include <fstream>
#include <cmath>
#include <vector>
#include<iostream>
using namespace std;

const int NMAX = 1e6+5;

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

bool ciur[NMAX];
vector<int> prime;
int N;
long long a,b;

void faciur() {
    ciur[0] = ciur[1] = 1;
    for (int i = 2; i*i<NMAX; i++) {
        if (ciur[i] == 0) {
            for (int j = i*i; j<NMAX; j+=i) {
                ciur[j] = 1;
            }
        }
    }
    for (int i = 2; i<NMAX; i++) {
        if (ciur[i] == 0) prime.push_back(i);
    }
}

int main() {
    faciur();
    fin >> N;
    while (N--) {
        fin >> a >> b;
        vector<int> fact;
        long long ans = 0;
        int d = 0;
        while (b > 1) {
            bool ok = 0;
            while (b % prime[d] == 0) {
                b /= prime[d];
                ok = 1;
            }
            if (ok) fact.push_back(prime[d]);
            if (b > 1 && prime[d]*prime[d] > b) {
                fact.push_back(b);
                b = 1;
            }
            d++;
        }
        int nrfact = fact.size();
        for (int mask = 0; mask < (1<<nrfact); mask++) {
            long long p = 1;
            for (int j = 0; j<nrfact; j++) {
                if (mask & (1<<j)) {
                    p *= 1LL * fact[j];
                }
            }
            int nrb = __builtin_popcount(mask);
            if (nrb%2 == 0) {
                ans += a/p;
            } else {
                ans -= a/p;
            }
        }
        
        fout << ans << "\n";
    }
    
  
    return 0;
}