#include<cstdio>
#include<bitset>
#include<vector>

using namespace std;

typedef long long int lld;
const int AMAX = 1000000;

int M;
lld A,B,Solution;
bitset<AMAX/2+5> Sieve;
vector<int> Primes;
vector<lld> Decomposition;

void Read(),Precompute(),Solve();

void Back(int top,lld value,int ok)
{
    if(top == (int)Decomposition.size())
    {
        Solution += ok * (A/value);
        return;
    }

    Back(top+1, value, ok);
    Back(top+1, value * Decomposition[top], -ok);
}

int main()
{
    Read();
    Precompute();
    Solve();

    return 0;
}

void Read()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%d",&M);
}

void Precompute()
{
    int i,j,k;

    Primes.push_back(2);

    for(i = 3, j = 1; i*i <= AMAX; i += 2, j++)
        if(!Sieve[j])
        {
            Primes.push_back(i);
            for(k = i*i/2; 2*k+1 <= AMAX; k += i)
                Sieve[k] = 1;
        }

    for(; i <= AMAX; i += 2, j++)
        if(!Sieve[j]) Primes.push_back(i);
}

void Solve()
{
    vector<int>::iterator it;
    int p;

    for(; M; --M)
    {
        scanf("%lld%lld",&A,&B);

        Solution = 0;
        Decomposition.resize(0);

        for(it = Primes.begin(); it != Primes.end() && B > 1; it++)
        {
            for(p = 0; B%(*it) == 0; p++, B /= (*it));
            if(p) Decomposition.push_back(*it);
        }

        if(B > 1) Decomposition.push_back(B);

        Back(0,1LL,1);

        printf("%lld\n",Solution);
    }
}