//Include
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

//Constante
const int sz = (int)1e6+2;

//Definitii
#define ll long long int
#define pb push_back

//Functii
void eratosthenes();

//Variabile
int questions;
ll num, primeWith;

vector<int> primeNumbers, divisors;

//Main
int main()
{
	eratosthenes();

    in >> questions;
    while(questions--)
    {
        in >> num >> primeWith;
        ll answer = 0;
        vector<int>::iterator it, end = primeNumbers.end();
        for(it=primeNumbers.begin(); it!=end && *it<=primeWith; ++it)
            if(!(primeWith%*it))
            {
                divisors.pb(*it);
                while(!(primeWith%*it))
                    primeWith/=*it;
            }

        if(primeWith != 1)
            primeNumbers.pb(primeWith);

        ll limit = 1LL<<divisors.size();
        for(int i=1; i<limit; ++i)
        {
            int bits = 0;
            ll prod = 1LL;
            for(int j=0; (1<<j)<=i; ++j)
                if((1<<j)&i)
                {
                    ++bits;
                    prod *= divisors[j];
                }

            if(bits & 1)
                answer += num/prod;
            else answer -= num/prod;
        }

        out << num - answer << "\n";

        divisors.clear();
    }

	in.close();
	out.close();
	return 0;
}

void eratosthenes()
{
    bool notPrime[sz];
    memset(notPrime, false, sizeof(notPrime));

    primeNumbers.pb(2);
    for(int i=3; i<sz; i+=2)
    {
        if(!notPrime[i])
        {
            for(int j=i+i; j<sz ;j+=i)
                notPrime[j] = true;
            primeNumbers.pb(i);
        }
    }
}