#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;

    for(long long i=1; i<=nr_prime[0]; i++)
        if(b % nr_prime[i] == 0) d[++d[0]] = nr_prime[i];

    for(int i = 1; i < (1 << d[0]); i++) {
        long long semn = 0, prod = 1;
        for(int j = 0; j < d[0]; 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 + d[0], 0);
}

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

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