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

using namespace std;

vector <int> prime;

void ciurul()
{
    const int VMAX = 1e6;
    bitset <1+VMAX> c;
    for (int i = 3; i * i < VMAX; i+=2)
    {
        if (!c[i])
        {
            for (int mult = i * i; mult <= VMAX; mult += i)
            {
                c[mult] = 1;
            }
        }
    }
    prime.push_back(2);
    prime.push_back(3);
    for (int i = 5; i <= VMAX; i+=6)
    {
        if (!c[i])
        {
            prime.push_back(i);
        }
        if (!c[i+2])
        {
            prime.push_back(i+2);
        }
    }
}

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

long long prime_cu_b(long long a, long long b)
{
    vector <long long> d;
    desc(b, d);
    int n = (int)d.size();///nr. de div. primi ai lui b
    long long rez = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        long long p = 1;
        int nb = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))///d[j] apartine submultimii codif. de i
            {
                p *= d[j];
                nb++;
            }
        }
        if (nb % 2 == 0)
        {
            rez += a / p;
        }
        else
        {
            rez -= a / p;
        }
    }
    return rez;
}

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