#include <fstream>
#include <vector>
#include <cmath>

#define MAX 1000000
using namespace std;

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

typedef unsigned long long ull;

ull dp[2][200005], st[2][200005], nr[3], rez;
bool ciur[MAX + 5];
vector<int> prime, toIt;

void make_ciur()
{
    for(ull i = 2; i <= MAX; ++i)
        if(ciur[i] == 0)
        {
            prime.push_back(i);
            for(ull j = i + i; j <= MAX; j += i)
                ciur[j] = 1;
        }
}

void compute(ull A, ull B)
{
    ull cB = B;
    toIt.clear();
    toIt.push_back(-1);
    for(int i = 0; i < prime.size() && prime[i] <= B; ++i)
    {
        if(B % prime[i] == 0)
        {
            dp[0][++nr[0]] = prime[i];
            st[0][nr[0]] = nr[0];
            rez += A / prime[i];
            toIt.push_back(prime[i]);
            while(cB % prime[i] == 0)
                cB /= prime[i];
        }
        else if(prime[i] > sqrt(cB) && cB != 1)
        {
            dp[0][++nr[0]] = cB;
            st[0][nr[0]] = nr[0];
            rez += A / cB;
            toIt.push_back(cB);
            return;
        }
    }
}

int main()
{
    make_ciur();

    int m;
    fin >> m;

    while(m--)
    {
        ull A, B;
        fin >> A >> B;

        nr[0] = nr[1] = 0;
        rez = 0;
        compute(A, B);
        int curLine = 1, lastLine = 0;
        int lim = nr[0];
        for(int pas = 2; pas <= lim; ++pas)
        {
            for(int i = 1; i <= nr[lastLine]; ++i)
                for(int j = st[lastLine][i] + 1; j <= lim; ++j)
                    if(dp[lastLine][i] * toIt[j] <= A)
                    {
                        dp[curLine][++nr[curLine]] = dp[lastLine][i] * toIt[j];
                        st[curLine][nr[curLine]] = j;
                        if(pas % 2 == 0)
                            rez -= A / dp[curLine][nr[curLine]];
                        else rez += A / dp[curLine][nr[curLine]];
                    }
                    else break;
            nr[lastLine] = 0;
            curLine = 1 - curLine;
            lastLine = 1 - lastLine;
        }
        fout << A - rez << '\n';
    }
    return 0;
}