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

using namespace std;

const int RMAX = 1e6;

vector <int> p;

void ciurul()
{
    bitset <RMAX+1> c;
    for (int d = 2; d * d <= RMAX; d++)
    {
        if (!c[d])
        {
            for (int m = d * d; m <= RMAX; m += d)
            {
                c[m] = 1;
            }
        }
    }
    for (int i = 2; i <= RMAX; i++)
    {
        if (!c[i])
        {
            p.push_back(i);
        }
    }
}

void descompunere(long long n, vector <long long> &d)
{
    int np = (int)p.size(), i = 0;
    while (i < np && (long long)p[i] * p[i] <= n)
    {
        if (n % p[i] == 0)
        {
            d.push_back(p[i]);
            while (n % p[i] == 0)
            {
                n /= p[i];
            }
        }
        i++;
    }
    if (n != 1)
    {
        d.push_back(n);
    }
}

long long pinex(long long x, vector <long long> &dp)
{
    int ndp = (int)dp.size();
    long long nr = 0;
    for (int m = 0; m < (1 << ndp); m++)
    {
        long long prod = 1;
        bool adun = true;
        for (int i = 0; i < ndp; i++)
        {
            if (m & (1 << i))
            {
                prod *= dp[i];
                adun = (!adun);
            }
        }
        if (adun)
        {
            nr += x / prod;
        }
        else
        {
            nr -= x / prod;
        }
    }
    return nr;
}

long long numar(long long x, long long n)
{
    vector <long long> dp;
    descompunere(n, dp);
    return pinex(x, dp);
}

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    ciurul();
    int q;
    in >> q;
    for (int i = 0; i < q; i++)
    {
        long long x, n;
        in >> x >> n;
        out << numar(x, n) << "\n";
    }
    in.close();
    out.close();
    return 0;
}