#include <bits/stdc++.h>

using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
const int Nmax = 1000005;
const int Pmax = 20;
int Q, prime[Nmax / 10], k, st[Pmax], dim, nrdiv[Pmax];
long long sol, s, A, B;
bitset < Nmax > a;
inline void CIUR()
{
    a[1] = 1;
    for(int i = 4 ; i <= Nmax - 5 ; i += 2)
        a[i] = 1;
    for(int i = 3 ; i * i <= Nmax - 5 ; i += 2)
        if(a[i] == 0)
            for(int j = i * i ; j <= Nmax - 5 ; j += 2 * i)
                a[j] = 1;
    k = 1;
    prime[k] = 2;
    for(int i = 3 ; i <= Nmax - 5 ; i += 2)
        if(a[i] == 0)
            prime[++k] = i;
}
inline void Desc()
{
    int d, i;
    i = 1;
    d = prime[i];
    dim = 0;
    while(B > 1 && 1LL * d * d <= B && i <= k)
    {
        if(B % d == 0)
        {
            ++dim;
            nrdiv[dim] = d;
            while(B % d == 0)
                B /= d;
        }
        i++;
        d = prime[i];
    }
    if(B > 1)
    {
        ++dim;
        nrdiv[dim] = B;
    }
}
void Back(int top)
{
    int nr1;
    if(top == (dim + 1))
    {
        nr1 = 0;
        s = 1;
        for(int i = 1 ; i <= dim ; i++)
        {
            if(st[i] == 1)
            {
                s = 1LL * s * nrdiv[i];
                nr1++;
            }

        }
        if(nr1 > 0)
        {
            if(nr1 % 2 == 1)
                sol += A / s;
            else sol -= A / s;
        }
    }
    else for(int i = 0 ; i <= 1 ; i++)
        {
            st[top] = i;
            Back(top + 1);
        }
}
int main()
{
    CIUR();
    fin >> Q;
    while(Q -- )
    {
        fin >> A >> B;
        Desc();
        sol = 0;
        Back(1);
        fout << A - sol << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}