//Include
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

FILE *in, *out;

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

//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()
{
	in = fopen("pinex.in", "rt");
	out = fopen("pinex.out", "wt");

	eratosthenes();

    fscanf(in,"%d", &questions);
    while(questions--)
    {
        fscanf(in,"%lld%lld", &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; j<=i; ++j)
                if((1<<j)&i)
                {
                    ++bits;
                    prod *= divisors[j];
                }

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

        fprintf(out,"%lld\n", num - answer);

        divisors.clear();
    }

	fclose(in);
	fclose(out);
	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);
        }
    }
}