#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int Primemax = 1000000;

vector <int> primenrs;
vector <long long> divs;
int t;
long long a, b;
bool e[Primemax + 5];

void Eratostene(){
    for (int i = 2; i <= Primemax; i++)
        if (!e[i]){
            primenrs.push_back(i);
            for (int j = 2 * i; j <= Primemax; j += i)
                e[j] = 1;
        }
}

void PrimeDivisors(){
    for (int i = 0; i < primenrs.size() && primenrs[i] * primenrs[i] <= b; i++)
        if (!(b % primenrs[i])){
            while (!(b % primenrs[i]))
                b /= primenrs[i];
            divs.push_back(primenrs[i]);
        }
    if (b > 1)
        divs.push_back(b);
}

long long Pinex(){
    long long ans = 0;
    for (int i = 1; i < (1 << divs.size()); i++){
        long long divisor = 1;
        int sign = -1;
        for (int j = 0; j < divs.size(); j++)
            if ((1 << j) & i){
                sign *= -1;
                divisor *= divs[j];
            }
        ans += a / divisor * sign;
    }
    return ans;
}

int main(){
    fin >> t;
    Eratostene();
    while (t--){
        fin >> a >> b;
        PrimeDivisors();
        fout << a - Pinex() << '\n';
        divs.clear();
    }
    return 0;
}