#include <bits/stdc++.h>
#define DIM 110001
#define int long long

using namespace std;

ifstream fin("pinex.in");

ofstream fout("pinex.out");

vector <int> v;

int Q, a, b;

int solve(int a, int b){

    v.clear();

    int answer = 0;

    int d = 2;

    while(b > 1){

        if(b % d == 0){

            v.push_back(d);

            while(b % d == 0)

                b /= d;

        }

        if(d >= 3)

            d += 2;

        else d++;

        if(d * d > b && b > 1)

            d = b;

    }

    for(int mask = 1 ; mask <= (1LL << v.size()) - 1; mask++){

        int prod = 1;

        for(int i = 0 ; i < v.size() ; i++)

            if((mask >> i) & 1)

            prod *= v[i];

        if(__builtin_popcount(mask) % 2 == 1)

            answer += (a / prod);

        else answer -= (a / prod);

    }

    return answer;

}

int32_t main(){

    fin >> Q;

    while(Q--){

        fin >> a >> b;

        fout << a - solve(a, b) << "\n";

    }

}