#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 5e6 + 5;
const int inf = 1e9 + 5;
const int mod = 100003;
using zint = int;

ll T,N,B;
ll primes[100];

ll getPhi(ll N,ll B);

int main() {
    in>>T;
    while (T--) {
        in>>N>>B;

        out<<getPhi(N,B)<<'\n';
    }

    in.close();out.close();
    return 0;
}

ll getPhi(ll N,ll B) {
    int nrPrimes = 0;

    ll aux = B;
    for (ll i=2;i*i <= aux;++i) {
        if (aux % i != 0) {
            continue;
        }

        while (aux % i == 0) {
            aux /= i;
        }

        primes[++nrPrimes] = i;
    }
    if (aux != 1) {
        primes[++nrPrimes] = aux;
    }

    /*
    pv(B),pn;
    for (int i=1;i <= nrPrimes;++i) {
        pv(primes[i]);
    }
    pn;
    //*/

    ll lim = 1<<nrPrimes, total = 0;
    for (ll mask = 1;mask < lim;++mask) {

        ll prod = 1,nr = 0;
        for (ll i=1;i <= nrPrimes;++i) {
            if (((1<<(i-1)) & mask) != 0) {
                prod *= primes[i];
                ++nr;
            }
        }

        //pv(prod);
        ll card = (nr % 2 == 1) ? N/prod : -N/prod;
        total += card;
    }
    //pn;

    return N - total;
}