#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
ofstream fout("pinex.out");
ifstream fin("pinex.in");
const int NMAX = 1000000, MMAX = 85000;

int n, nr_prime[MMAX];
long long a, b, d[NMAX];
bitset<NMAX> ciur;

void prime()
{
    ciur[0] = ciur[1] = 0;
    for(int i=2; i<NMAX; i++) {
        if(ciur[i]) {
            for(int j=i+i; j<NMAX; j+=i)
                ciur[j] = 0;
            nr_prime[++nr_prime[0]] = i;
        }
    }
}

void solve()
{
    long long sol = 0, c = 0, lg = 0;

    while (b > 1) {
        lg++;
        if (b % nr_prime[lg] == 0) {
            d[++c] = nr_prime[lg];
            while (b % nr_prime[lg] == 0)
                b /= nr_prime[lg];
        }

        if (nr_prime[lg] > sqrt(b) && b > 1) {
            d[++c] = b;
            b = 1;
        }
    }

    for(int i = 1; i < (1 << c); i++) {
        long long semn = 0, prod = 1;
        for(int j = 0; j < c; j++)
            if((1 << j) & i)
                prod = 1LL * prod * d[j+1], semn++;

        if(semn & 1) semn = 1;
        else semn = -1;

        sol = sol + 1LL * semn * a / prod;
    }

    fout << a - sol << '\n';
    fill(d, d + c, 0);
}

int main()
{
    fin >> n;
    ciur.set();
    prime();

    for(int i=1; i<=n; i++) fin >> a >> b, solve();
    return 0;
}