#include <fstream>
#include <vector>

using namespace std;

const int MAXP = 1e6 + 1, NDIV = 13;

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

int t, x[NDIV];
long long a, b, sol;
bool v[MAXP];
vector<int> pr, divi;

void ciur()
{
    for(int i = 4; i < MAXP; i += 2) v[i] = 1;
    for(int i = 3; i * i < MAXP; i += 2)
        if(!v[i]) for(int j = i * i; j < MAXP; j += i) v[j] = 1;
    pr.push_back(2);
    for(int i = 3; i < MAXP; i += 2) if(!v[i]) pr.push_back(i);
}

void genDiv()
{
    divi.clear();
    for(int i = 0; 1LL * pr[i]*pr[i] <= b; ++i)
        if(b % pr[i] == 0)
        {
            divi.push_back(pr[i]);
            do
            {
                b /= pr[i];
            }
            while(b % pr[i] == 0);
        }
    if(b > 1) divi.push_back(b);
}

void bt(int k, long long prod)
{
    for(int i = x[k - 1] + 1; i < divi.size(); ++i)
    {
        x[k] = i;
        sol += (k & 1 ? a / (prod * divi[i]) : -a / (prod * divi[i]));
        bt(k + 1, prod * divi[i]);
    }
}

int main()
{
    ciur();
    fin >> t;
    while(t--)
    {
        fin >> a >> b;
        genDiv();
        sol = 0;
        x[0] = -1;
        bt(1, 1LL);
        fout << a - sol << '\n';
    }
    return 0;
}