#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vc;
typedef vector<vector<int>> matrix;
#define ft(n) for(ull i=1; i<=n; i++)
#define sp ' '
string file = "pinex";
ifstream f(file + ".in");
ofstream g(file + ".out");

int n;
ll a, b, res;

const int ciurmax = 1e6; //already sqrt
bool notprime[ciurmax + 5];
vector<int> primes(1, 2);
void ciur()
{
    for (int i = 4; i <= ciurmax; i += 2)
        notprime[i] = 1;
    for (int i = 3; i <= ciurmax; i += 2)
        if (notprime[i] == 0)
        {
            primes.push_back(i);
            for (int j = 2 * i; j <= ciurmax; j += i)
                notprime[j] = 1;
        }
}

void desc(ll n, vc& v)
{
    for (int d : primes)
    {
        if (d > n)
            break;
        if (n % d == 0)
            v.push_back(d);
        while (n % d == 0)
            n /= d;
    }
    if (n > 1)
        v.push_back(n); //b has a prime factor bigger than sqrt(10^12)
}

void bkt(int n, vc v)
{
    int nr = (1 << n);
    for (int i = 1; i < nr; i++)
    {
        bitset<20> x(i);
        ll prod = 1;
        for (int j = 0; j < n; j++)
            if (x[j] == 1)
                prod *= v[j]; //no lcm needed
        int semn = 1;
        if (x.count() % 2 == 1)
            semn = -1;
        res += semn * a / prod;
    }
}

void pinex(ll a, ll b)
{
    vector<int> pfactors; //can only have at most ~15 prime factors
    desc(b, pfactors);
    res = a;
    bkt(pfactors.size(), pfactors);
    g << res << '\n';
}

int main()
{
    ciur();
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> a >> b;
        pinex(a, b);
    }
    return 0;
}