#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) {
            prime.push_back(i);
            for (int j = i*i; j<NMAX; j+=i) {
                ciur[j] = 1;
            }
        }
    }
}

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