#include <bits/stdc++.h>
using namespace std;

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

int m;

int ciur[1000005];

vector <long long> valori;
void precalc()
{
    valori.push_back(2);
    for (long long i = 3; i <= 1000000; i+= 2)
    {
        if(ciur[i] == 0)
        {
            valori.push_back(i);
            for (long long j = i * i; j <= 1000000; j += i + i)
            {
                ciur[j] = 1;
            }
        }
    }
}

void factori(long long n, vector<long long>& fact)
{
    int i = 0;
    long long d = valori[i];
    while (n > 1)
    {
        if (n % d == 0)
        {
            while (n % d == 0)
            {
                n /= d;
            }
            fact.push_back(d);
        }

        d = valori[++i];

        if (d * d > n)
        {
            d = n;
        }
    }
}

long long raspuns;
void backtrack(int poz, int l, vector<long long>& fact, long long p, long long& a)
{
    if (l == fact.size())
    {
        if (poz == 0) return;
        if (poz % 2 == 0) raspuns -= a / p;
        else raspuns += a / p;

        return;
    }

    backtrack(poz, l + 1, fact, p, a);


    backtrack(poz + 1, l + 1, fact, p * fact[l], a);



}

void solve(long long a, long long b)
{
    vector <long long> fact;
    factori(b, fact);

    raspuns = 0;
    backtrack(0, 0, fact, 1, a);
    out << a - raspuns << "\n";

}

int main()
{
    precalc();
    in >> m;

    for (int i = 1; i <= m; i++)
    {
        long long a, b;
        in >> a >> b;

        solve(a, b);
    }


    return 0;
}