#include <fstream>
#include <iostream>

using namespace std;

typedef long long ll;

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

const int NMAX = 1000001,
          PRIME = 78498;
bool p[NMAX+2];
int nrP = 1, pr[PRIME+3],
    f[30];

void ciur() {
    for(int i = 4; i <= NMAX; i += 2)
        p[i] = 1;
    for(int i = 3; i*i <= NMAX; i += 2)
        if(p[i] == 0)
            for(int j = i*i; j <= NMAX; j += i)
                p[j] = 1;

    pr[1] = 2;
    for(int i = 3; i <= NMAX; i += 2)
        if(p[i] == 0) pr[++nrP] = i;
}

void solve(ll a, ll b) {
    short nrF = 0;
    for(int i = 1; pr[i]*pr[i] <= b && i <= nrP; i++) {
        if(b%pr[i] == 0) {
            f[++nrF] = pr[i];
            while(b%pr[i] == 0) b /= pr[i];
        }
    }
    if(b > 1)
        f[++nrF] = b;

    ll s = a;
    for(int i = 1; i < (1 << nrF); i++) {
        int nr = 0;
        ll p = 1;
        for(int j = 0; j < nrF; j++)
            if((1 << j) & i) {
                p *= f[j+1];
                nr++;
            }
        if(nr%2 == 0) s += a/p;
        else s -= a/p;
    }
    out << s << '\n';
}

int main()
{
    ciur();
    int m;
    ll a, b;
    in >> m;
    while(m--) {
        in >> a >> b;
        solve(a, b);
    }
    return 0;
}