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

using namespace std;

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

const long long N = 1000005;

long long m, a, b;
bool ciur[N];
vector <int> divizori, divizoriB;

void leCiur(){
    for(int i = 2; i <= N; i++){
        if(!ciur[i]){
            for(int d = i * 2; d <= N; d += i)
                ciur[d] = 1;
            divizori.push_back(i);
        }
    }
}

void solve(){

    long long len = divizori.size();

    for(int i = 0; i < len && divizori[i] * divizori[i] <= b; i++){
        int div = divizori[i];
        if(b % div == 0){
            while(b % div == 0){
                b/= div;
            }
            divizoriB.push_back(div);
        }
    }
    if(b != 1)
        divizoriB.push_back(b);

    long long sol =  a;

    int lenB = divizoriB.size();

    for(int i = 1; i < (1 << lenB); i++){
        long long exp = 0, produs = 1;

        for(int j = 0; j < lenB; j++){
            if((1 << j) & i){
                produs = produs * divizoriB[j];
                exp++;
            }
        }

        if(exp % 2 == 1)
            exp = -1;
        else
            exp = 1;

        sol = sol + exp * a / produs;
    }

    out << sol << "\n";

}


int main() {

    ios::sync_with_stdio(false);

    leCiur();

    in >> m;

    for(int i = 0; i < m; i++){
        divizoriB.clear();
        in >> a >> b;
        solve();
    }
    /// divizorii primi ai lui b
    /// aduni multiplii fiecaruia divizor mai mici decat a
    /// scazi comb de 2
    /// aduni combinatii de 3

    return 0;
}