#include <bits/stdc++.h>

#pragma GCC optimize("O2")

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

//#define fin std::cin 
//#define fout std::cout

const int lim = 1e6;


int t;
int A, B;

std::vector<int> prime;

void precalc_primes()
{
    bool ciur[lim + 1];
    ciur[0] = ciur[1] = true;
    for(int i = 2; i * i <= lim; ++i)
        if(!ciur[i])
            for(int j = 2 * i; j <= lim; j += i)
                ciur[j] = true;

    for(int i = 2; i <= lim; ++i)
        if(!ciur[i])
            prime.emplace_back(i);
}



int main()
{
    
    std::ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    
    fin >> t;
    precalc_primes();

    while(t--)
    {
        fin >> A >> B;

        std::vector<int> primes_B;

        int idx = 0;
        while(B > 1)
        {
            if(B % prime[idx] == 0)
            {
                primes_B.emplace_back(prime[idx]);
                while(B % prime[idx] == 0)
                    B /= prime[idx];
            }

            idx++;
            if(prime[idx] * prime[idx] > B && B > 1)
            {
                primes_B.emplace_back(B);
                break;
            }
        }

        int b_size = primes_B.size();
        int64_t ans = A;

        for(int i = 1; i < (1 << b_size); ++i)
        {
            int sign = -1;
            int64_t prod = 1;

            for(int j = 0; j < b_size; ++j)
            {
                int good = ((i >> j) & 1);
                if(good)
                    sign *= -1, prod *= primes_B[j];
            }
            ans -= sign * (A / prod);
        }

        fout << ans << "\n";
    }

    return 0;
}