#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
#define MAXDIV 1000009
FILE *g=fopen("pinex.out","w");
bitset <MAXDIV+1> prim;
vector<long long> nprime,nr;
long long a,b;

void ciur() { 
	long long i,j;
	for(i=2; i<=MAXDIV; i++) prim[i]=1;
	for(i=2; i<=MAXDIV; i++)
		if(prim[i]==1){
			nprime.push_back(i);
			for(j=i+i; j<=MAXDIV; j+=i) {
				prim[j]=0;
			}
		}
}

void divizori() {
	int M,semn;
    long long prod,sum;
    nr.clear();
    vector<long long>::iterator it;

    M=0;
    for(it=nprime.begin(); it!=nprime.end() && (*it)*(*it) <= b ;++it)
        if (b%(*it)==0)
            {
            nr.push_back(*it);
            ++M;
            for(; b%(*it)==0 ; b/=(*it));
            }
    if (b>1)
        {
        nr.push_back(b);
        ++M;
        }

    sum=0;
    for(long long i=1;i<(1<<M);++i)
        {
        prod=1;
        semn=0;
        for(int j=0;j<M;++j)
            if (i&(1<<j))
                {
                semn^=1;
                prod*=(long long)nr[j];
                }
        if (semn)
            sum += (a/prod);
        else
            sum -= (a/prod);
        }
   fprintf(g,"%lld\n",a-sum);
}



int main()
{
	int m,i;
	FILE *f=fopen("pinex.in","r");
	ciur();
	fscanf(f,"%d",&m);
	for(i=0; i<m; i++) {
		fscanf(f,"%lld %lld", &a, &b);
		divizori();
	}
	fclose(f);
	fclose(g);
	return 0;
}