#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <cstring>
#include <stack>
#include <cmath>
#include <queue>
#include <fstream>

using namespace std;

const int ciur_dim = 1000000;

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

bool ciur[ciur_dim];
vector <int> prime;
vector <long long int> factori;

long long int a,b;
int k,st[ciur_dim],semn;
long long int prod,n;
long long int sol;

void Fa_Ciur()
{
    int i,j;
    for (i=2; i<ciur_dim; i++)
    {
        if (ciur[i] == 0)
        {
            prime.push_back(i);
            for (j=2*i; j<ciur_dim; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
}

void Afisare()
{
    prod = 1;
    for (int i=1; i<=k; i++)
    {
        prod *= factori[st[i]];
    }
    sol = sol + semn*a/prod;
}

void Back(int top)
{
    if (top == k)
    {
        Afisare();
    }
    else
    {
        for (int i = st[top]+1; i<=n-k+top; i++)
        {
            st[top+1] = i;
            Back(top+1);
        }
    }
}

void Rezolva()
{
    int it = 0,i;
    factori.clear();
    factori.push_back(0);
    while (b > 1)
    {
        if (b%prime[it] == 0)
        {
            factori.push_back(prime[it]);
            while (b%prime[it] == 0)
            {
                b /= prime[it];
            }
        }
        if (prime[it] > sqrt(b) && b != 1)
        {
            factori.push_back(b);
            b = 1;
        }
        it++;
    }
    sol = 0;
    n = factori.size();
    for (i=1; i<=n; i++)
    {
        k = i;
        if ((i-1)%2 == 0)
        {
            semn = 1;
        }
        else
            semn = -1;
        Back(0);
    }
   out << a-sol << "\n";
}

int main()
{
    long long int q;
    Fa_Ciur();
    in >> q;
    for (int i=1; i<=q; i++)
    {
        in >> a >> b;
        Rezolva();
    }
    return 0;
}