#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
typedef long long num;
const num number_of_primes = 1000001;
num primes[80000];

void generate_primes()
{
    num l = 0;
    bool isPrime[number_of_primes];
    fill(isPrime+2,isPrime+number_of_primes,true);
    for(num i = 2; i < number_of_primes; i++)
        isPrime[i] = true;

    for(num p = 2; p < number_of_primes; p++)
        if(isPrime[p])
        {
            primes[++l] = p;
            for(num i = p * 2; i <= number_of_primes ; i += p)
                isPrime[i] = false;
        }
}

void backtracking(num set[], num n, num A)
{
    num S = 0;
    for(num i = 1; i < (1 << n); i++)
    {
        num P = 1;
        bool odd = false;
        for(num j = 0; j < n; j++)
            if(i & (1 << j) )
            {
                P *= set[j+1];
                odd = !odd;
            }
        if(odd)
            S += A / P;
        else
            S -= A / P;
    }
    fout << A - S << '\n';
}

void prime_decomposition(num m, num factors[], num &number_of_factors)
{
    number_of_factors = 0;
    for(num i = 1; primes[i]*primes[i] <= m; i++)
        if(m % primes[i] == 0)
        {
            factors[++number_of_factors] = primes[i];
            while(m % primes[i] == 0)
                m /= primes[i];
        }
    if ( m != 1)
        factors[++number_of_factors] = m;
}

int main()
{
    generate_primes();
    num M;
    for(fin >> M; M; M--)
    {
        num A, B;
        fin >> A >> B;

        num factorts_of_B[60];
        num nr_factors;
        prime_decomposition(B, factorts_of_B, nr_factors);

        backtracking(factorts_of_B, nr_factors, A);
    }

    fin.close();
    fout.close();
    return 0;
}