#include <bits/stdc++.h>

using namespace std;

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

long long m, a, b, sum;
int f[1000005];

vector <int> primes;
vector <int> divisors;

void sieve()
{
    for ( int i = 2; i <= 1e6; ++i )
    {
        if ( f[i] == 0 )
        {
            for ( int j = i; j <= 1e6; j += i )
            {
                f[j] = 1;
                primes.push_back(j);
            }
        }
    }
}

void getDivisors()
{
    for ( auto x:primes )
    {
        if ( b%x == 0 )
        {
            divisors.push_back(x);

            while ( b%x == 0 )
                b /= x;
        }
    }

    if ( b > 1 )
        divisors.push_back(b);
}

void pinex()
{
    for ( int i = 1; i < (1<<divisors.size()); ++i )
    {
        long long product = 1;
        int k = 0;

        for ( int j = 0; j < divisors.size(); ++j )
        {
            if ( i&(1<<j) )
            {
                product *= divisors[j];
                k++;
            }
        }

        if ( k%2 )
            sum += a/product;
        else
            sum -= a/product;
    }

    fout<<a-sum<<'\n';
}

void resetValues ()
{
    sum = 0;
    divisors.clear();
}

int main()
{
    fin>>m;

    sieve();

    while ( m-- )
    {
        fin>>a>>b;

        getDivisors();
        pinex();
        resetValues();
    }
}