#include <fstream>
#include <vector>

using namespace std;

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

const long long NMax = 1e6;

long long Div[20], N, M, Sol, X[20], A, B;

bool Prim[NMax + 5];

vector <long long> P;

void Sieve()
{
    for(long long i = 2; i <= NMax; i++)
        if(Prim[i] == 0)
        {
            P.push_back(i);

            for(long long j = 2 * i; j <= NMax; j += i)
                Prim[j] = 1;
        }
}

void Decompose(long long K)
{
    N = 0;

    for(auto x : P)
    {
        if(x * x > K) break;

        if(K % x) continue;

        Div[++N] = x;

        while(K % x == 0)
            K /= x;
    }
    if(K > 1) Div[++N] = K;
}

void Back(long long k, long long Prod)
{
    for(long long i = X[k - 1] + 1; i <= N; i++)
    {
        long long s = ((k % 2) ? 1 : -1), d = Div[i];

        X[k] = i, Sol += s * (A / (Prod * d));

        if(k + 1 <= N)
            Back(k + 1, Prod * d);
    }
}

int main()
{
    fin >> M; Sieve();

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

        Sol = 0; Decompose(B); Back(1, 1);

        fout << A - Sol << '\n';
    }
    fin.close();
    fout.close();

    return 0;
}