#include <fstream>
#include <vector>

using namespace std;

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

bool ciur[1000100];
vector<long long> prime;
vector<long long> back;
vector<long long> backt;

void fac_ciur (){
    ciur[1] = 1;
    for (long long i=1; i<=1e6; i++){
        if (ciur[i] == 0){
            prime.push_back(i);
            for (long long j=i + i; j<= 1e6; j+=i){
                ciur[j] = 1;
            }
        }
    }
}

void backtracking(long long q, long long n, long long &s, long long a){
    if (q >= 1){
        long long impart = 1;
        long long cont = 0;
        for (auto x : backt){
            cont++;
            impart *= x;
        }
        if (cont % 2 == 0){
            s -= a/impart;
        }
        else{
            s += a/impart;
        }
    }
    if (q == n){
        return;
    }
    for (long long i=q; i<=back.size() - 1; i++){
        backt.push_back(back[i]);
        backtracking(i + 1, n, s, a);
        backt.pop_back();
    }
}

int main() {
    fac_ciur();
    long long t;
    cin>>t;
    while(t--){
        back.clear();
        long long a , b;
        cin>>a>>b;
        for (auto x : prime){
            if (x > min (a, b)){
                break;
            }
            if (b % x == 0){
                back.push_back(x);
                long long cx = x;
                while (b % cx == 0){
                    b /= cx;
                }
            }
        }
        if (b != 1){
            back.push_back(b);
        }
        long long s = 0;
        backtracking(0, back.size(), s, a);
        a -= s;
        cout<<a<<'\n';
    }
    return 0;
}