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

using namespace std;

const int VMAX = 1e6;

vector <int> prime;

void ciurul()
{
    bitset <1+VMAX> c;
    for (int i = 2; i * i <= VMAX; i++)
    {
        if (!c[i])
        {
            for (int multiplu = i * i; multiplu <= VMAX; multiplu += i)
            {
                c[multiplu] = 1;
            }
        }
    }
    for (int i = 2; i <= VMAX; i++)
    {
        if (!c[i])
        {
            prime.push_back(i);
        }
    }
}

void desc(long long n, vector <long long> &divi)
{
    unsigned int i = 0;
    while (i <  prime.size() && prime[i] * prime[i] <= n)
    {
        if (n % prime[i] == 0)
        {
            divi.push_back(prime[i]);
            while (n % prime[i] == 0)
            {
                n /= prime[i];
            }
        }
        i++;
    }
    if (n != 1)
    {
        divi.push_back(n);
    }
}

long long pinex(long long a, long long b)
{
    vector <long long> d;
    desc(b, d);
    unsigned int n = d.size();
    long long rez = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        int nr = 0;
        long long p = 1;
        for (unsigned int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                nr++;
                p *= d[j];
            }
        }
        if (nr % 2 == 0)
        {
            rez += a / p;
        }
        else
        {
            rez -= a / p;
        }
    }
    return rez;
}

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    ciurul();
    int m;
    in >> m;
    for (int i = 0; i < m; i++)
    {
        long long a, b;
        in >> a >> b;
        out << pinex(a, b) << "\n";
    }
    return 0;
}