#include <bits/stdc++.h>

using namespace std;

long long A, B;
vector <int> fact;

int gen(){
    int mask, rez, i, cnt, mobius;
    long long prod;

    rez = 0;
    for(mask = 1; mask < (1 << (fact.size())); mask++){
        cnt = 0;
        prod = 1;
        for(i = 0; i < fact.size(); i++){
            if((mask >> i) & 1){
                cnt++;
                prod *= fact[i];
            }
        }
        if(cnt % 2 == 1){
            mobius = 1;
        }else{
            mobius = -1;
        }
//        printf("mask = %d, prod = %d\n", mask, prod);
        rez += mobius * (A / prod);
    }
    return rez;
}

void test()
{
    int d;

    cin >> A >> B;
    while(!fact.empty()){
        fact.pop_back();
    }

    d = 2;
    while(d * d <= B){
        if(B % d == 0){
            fact.push_back(d);
            while(B % d == 0){
                B /= d;
            }
        }
        d++;
    }
    if(B){
        fact.push_back(B);
    }
    cout << A - gen() << "\n";
}
int main(){
    int t;
    cin >> t;
    while(t--){
        test();
    }
}