#include <fstream>
#include <vector>

using namespace std;

ifstream cin("pinex.in");
ofstream cout("pinex.out");

const int NMAX = 1e6;

int Q,A,B,sum;
vector<int> prime;
bool eprim[NMAX+1];


void eratostene()
{
    for(int i = 3; i <= NMAX; i+= 2)
    {
        if(eprim[i] == 0)
            for(int j = i + i; j <= NMAX; j += i)
                eprim[j] = 1;
    }

    prime.push_back(2);
    for(int i = 3; i <= NMAX; i++)
    {
        if(eprim[i] == 0 && i % 2)
            prime.push_back(i);
    }
}

void prod(int n, vector<int> &sub, vector<int> &factori)
{
    int P = 1;
    for(int i = 1; i <= n; i++)
        P *= factori[sub[i]];
    if(n % 2 == 1)
        sum += (A / P);
    else sum -= (A / P);
}

void Back(vector<int> &sub, int k, vector<int> &elem)
{
   for(int i = sub[k-1] + 1; i < elem.size(); i++)
   {
       sub[k] = i;
       prod(k, sub, elem);
       if(k < elem.size())
            Back(sub, k+1, elem);
   }
}

void solve()
{
    sum = 0;
    vector<int> factoriprimi;
    int ind = 0, d = prime[0];
    while(B != 1)
    {
        if(B % d == 0)
        {
            factoriprimi.push_back(d);
            while(B % d == 0)
                B /= d;
        }
        if(prime[ind+1] * prime[ind+1] > B)
            d = B;
        else d = prime[++ind];
    }
    vector<int> submultimi(factoriprimi.size());

//    for(int i = 0; i < factoriprimi.size(); i++)
//        cout << factoriprimi[i] << ' ';
//    cout << '\n';
    submultimi[0] = -1;
    Back(submultimi,1,factoriprimi);
    cout << A-sum << '\n';
}

int main()
{
    eratostene();
    cin >> Q;
    while(Q--)
    {
        cin >> A >> B;
        solve();
    }
}