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

using namespace std;

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

typedef unsigned long long ull;

vector<int> prime, toIt;
bool ciur[1000005];
ull nr[2], cnt, dp[2][200005], A, B, st[2][200005];
long long rez = 0;

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

void initializare()
{
    nr[0] = 0;
    nr[1] = 0;
    toIt.clear();
    toIt.push_back(-1);
    ull cB = B;
    for(int i = 1; i <= cnt && 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);
            break;
        }
    }
}

int main()
{
    make_ciur(1000000);

    ull m;
    fin >> m;

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

        rez = 0;
        initializare();
        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;
}