#include<iostream>
#include<fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long fun(long a,long b)
{
	if(b==0)
		return a;
	else
		return fun(b,a%b);
}
int main()
{
	long n,i,x,y,j,c=0;
	f>>n;
	for(i=1;i<=n;i++)
	{
		f>>x>>y;
		c=1;
		for(j=2;j<=x;j++)
			if(fun(j,y)==1)
				c++;
			g<<c<<"\n";
	}
	f.close();
	g.close();
	return 0;
}