#include <fstream>
#include <vector>

using namespace std;

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

bool d[1000000 + 5];
vector <long long> primes;

void Erathostenes()
{
    primes.push_back(2);

    for(int i = 3; i * i <= 1000000; i += 2)
        if(!d[i])
        {
            for(int j = i * i; j <= 1000000; j += 2 * i)
                d[j] = 1;
        }

    for(int i = 3; i <= 1000000; i += 2)
        if(!d[i])
            primes.push_back(i);
}

int main()
{
    Erathostenes();

    int M;
    fin >> M;

    for(int i = 1; i <= M; i++)
    {
        long long A, B;
        fin >> A >> B;

        vector <long long> div;

        for(auto it : primes)
            if(it > B)
                break;
            else if(B % it == 0)
                div.push_back(it), B /= it;

        if(B != 1)
            div.push_back(B);

        long long ans = A;

        for(int mask = 1; mask < (1 << (int)div.size()); mask++)
        {
            int sgn = 1;
            long long prod = 1LL;

            for(int bit = 0; bit < (int)div.size(); bit++)
                if(mask & (1 << bit))
                {
                    sgn *= (-1);
                    prod *= div[bit];
                }

            ans += sgn * (A / prod);
        }

        fout << ans << '\n';
    }

    return 0;
}