#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

const int N = 1e6;

vector <int> v;

void ciur ()
{
    bitset <N + 2> c;
    for (int i = 3; i * i <= N; ++i)
        if(!c[i])
            for (int j = i * i; j <= N; j += (i << 1))
                c[j] = 1;
    v.push_back(2);
    for (int i = 3; i <= N; i += 2)
        if (!c[i])
            v.push_back(i);
}
int n, a, b;

void desc (int x, vector <int> &d)
{
    for (int i = 0; i < v.size() && v[i] * v[i] <= x; ++i)
    {
        if (!(x % v[i]))
        {
            d.push_back(v[i]);
            while (!(x % v[i]))
                x /= v[i];
        }
    }
    if (x > 1)
        d.push_back(x);
}

int sol(int x, int y)
{
    vector <int> d;
    desc(y, d);
   // for (int i = 0; i < d.size(); ++i)
        //cout << d[i] << ' ';
   // cout << '\n';
    int na = d.size();
    long long sum = x;
    for (int i = 1; i < (1 << na); ++i)
    {
        int nr = 0;
        long long p = 1;
        for (int j = 0; j < na; ++j)
        {
            if (i & (1 << j))
            {
                ++nr;
                p *= d[j];
            }
            nr & 1 ? sum -= x / p : sum += x / p;
        }
    }
    return sum;


}

int main()
{
    ciur();
    for (cin >> n; n; --n)
    {
        cin >> a >> b;
        int sum = sol(a, b);
        cout << sum << '\n';
    }
    return 0;
}