#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m, stiva[78499];
bool isPrim[1000007];
long long a, b, d[78499], prime_numbers[78499], z, rez;

void Ciur()
{
    isPrim[0] = isPrim[1] = true;
    for (int i = 4; i <= 1000000; i += 2) isPrim[i] = true;
    for (int i = 3; i * i <= 1000000; i += 2)
    {
        if (!isPrim[i])
        {
            for (int j = i * i; j <= 1000000; j += 2 * i)
            {
                isPrim[j] = true;
            }
        }
    }
    prime_numbers[++z] = 2;
    for (int i = 3; i <= 1000000; i += 2)
    {
        if (isPrim[i] == false)
            prime_numbers[++z] = i;
    }
}

void Descompune(long long x)
{
    d[0] = rez = 0;
    for (int i = 1; prime_numbers[i] * prime_numbers[i] <= x && i <= z; ++i)
    {
        if (x % prime_numbers[i] == 0)
        {
            d[++d[0]] = prime_numbers[i];
            while (x % prime_numbers[i] == 0) x = x / prime_numbers[i];
        }
    }
    if (x > 1) d[++d[0]] = x;
}

void Back(int k, int maxim)
{
    if (maxim + 1 == k)
    {
        long long p = 1;
        for (int i = 1; i <= maxim; ++i)
        {
            p = p * d[stiva[i]];
        }
        if (maxim % 2 == 1) rez = rez + a / p;
        else rez = rez - a / p;
        return;
    }
    for (int i = stiva[k - 1] + 1; i <= d[0]; ++i)
    {
        stiva[k] = i;
        Back(k + 1, maxim);
    }
}

int main()
{
    Ciur();
    fin >> m;
    while (m--)
    {
        fin >> a >> b;
        Descompune(b);
        for (int i = 1; i <= d[0]; ++i)
        {
            stiva[1] = 0;
            Back(1, i);
        }
        fout << a - rez << "\n";
    }
    return 0;
}