#include <fstream>
#include <bitset>
#include <iostream>

#define NMAX 1000005
#define PMAX 79000

using namespace std;

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

int tests, nrPrime, nrDiv, i;
int divi[25], prime[PMAX];

long long int a, b, rez;

bitset <NMAX> ciur;
void ciurGenerator()
{
    ciur[1] = 1; ciur[0] = 1;

    for(int i = 2; i <= NMAX; i++)
    {
        if(ciur[i] == 0)
        {
            prime[nrPrime++] = i;

            for(int j = i; 1ll * i * j <= NMAX; j++)
                ciur[1ll * i * j] = 1;
        }
    }
}

void getDiv(long long int x)
{
    nrDiv = 0;

    for(int i = 0; prime[i] * prime[i] <= x && i < nrPrime; i++)
    {
        if(x % prime[i] == 0)
        {
            divi[nrDiv++] = prime[i];

            while(x % prime[i] == 0)
                x = x / prime[i];
        }
    }

    if(x > 1)
        divi[nrDiv++] = x;
}

void backTrack(int k, long long int prod, int ind)
{
    if(k > 0)
    {
        if(k % 2 == 1)
            rez += a / prod;
        else
            rez -= a / prod;
    }

    for(int i = ind; i < nrDiv; i++)
    {
        prod *= divi[i];
        backTrack(k + 1, prod, i + 1);
        prod /= divi[i];
    }
}

int main()
{
    f >> tests;

    ciurGenerator();
    while(tests)
    {
        f >> a >> b;

        getDiv(b);
        rez = 0;
        backTrack(0, 1, 0);

        g << a - rez << "\n";
        tests--;
    }

    return 0;
}