#include<fstreaM>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int n,a,i,nr,x,y,m,b,r,j;
int main()
{	f>>m; 
	while(m>0)
	{	f>>a>>b; nr=1;
		for(i=2;i<=a;i++)
		{	x=i; y=b;
			while(y) {r=x%y; x=y; y=r;}
			if(x==1) nr++;
		}
		g<<nr<<'\n';
		m--;
	}
	g.close(); return 0;
}