#include<fstream.h>
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,A,B,r,x,y,i,nr;
int main()
{
	f>>m;
	nr = 0;
	while((m))
	{
		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;
}