#include <fstream>
#include <vector>
#include <bitset>
#include <cmath>
#define infile "pinex.in"
#define outfile "pinex.out"

using namespace std;

typedef long long ll;

ifstream f(infile);
ofstream g(outfile);

void ciur();
vector<ll> find_div(ll);
void solve(ll, ll);

unsigned short t;

ll a, b;
vector<ll> prim;

int main()
{
    ciur();

    f >> t;

    while (t--)
    {
        f >> a >> b;

        solve(a, b);
    }

    return 0;
}

bitset<1000003> viz;
void ciur()
{
    for (int i = 2; i <= 1000000; ++i)
    {
        if (!viz[i]) {
            prim.emplace_back(i);
            for (int j = (i << 1); j <= 1000000; j+=i)
            {
                viz[j] = 1;
            }
        }
    }
}

vector<ll> find_div(ll x)
{
    vector<ll> ret;
    vector<ll>::iterator it = prim.begin();

    while (x != 1)
    {
        if (x % *it == 0) {
            ret.push_back(*it);
            while (x % *it == 0)
                x /= *it;
        }

        if (*it > sqrt(x) && x > 1)
            ret.push_back(x), x = 1;
        ++it;
    }

    return ret;
}

void solve(ll a, ll b)
{
    vector<ll> d = find_div(b);

    ll sol = a;
    ll n = (1 << (d.size()));
    for (int i = 1; i < n; ++i)
    {
        ll sign = 0;
        ll prod = 1;
        for (int j = 0; j < d.size(); ++j)
        {
            if ((1 << j) & i)
            {
                prod = 1LL * prod * d[j];
                ++sign;
            }
        }

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

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

    g << sol << '\n';
}