#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

vector <bool> c(1000001, 0);
vector <int> v;
vector <int> s;

int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    short M;
    int i, j, k;
    long long A, B, p;
    for(i=3; i<=1000000; i+=2)
	{
		if(c[i]==0)
		{
			for(j=3*i; j<=1000000; j+=2*i)
				c[j]=1;
		}
	}
	v.push_back(2);
	for(i=3; i<=1000000; i+=2)
		if(c[i]==0)
			v.push_back(i);
    fin>>M;
    for(i=1; i<=M; ++i)
	{
		fin>>A>>B;
		long long aux, rez=0;
		int r;
		for(j=0; j<v.size()&&v[j]<=B; ++j)
		{
			if(B%v[j]==0)
			{
				s.push_back(v[j]);
			}
		}
		for(j=0; j<(1<<s.size())-1; ++j)
		{
			p=j+1;
			aux=1;
			r=0;
			for(k=0; k<s.size()&&p!=0; ++k)
			{
				if(p&1)
				{
					aux*=s[k];
					r++;
				}
				p>>=1;
			}
			if(r&1)
				rez+=(A/aux);
			else
				rez-=(A/aux);
		}
		s.clear();
		fout<<A-rez<<'\n';
	}
    fin.close();
    fout.close();
    return 0;
}