#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned int usint;
unsigned int gcd(unsigned int a,unsigned int b)
{
	while(b^=a^=b^=a%=b);return a;
}
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	usint N,M;
	usint T,Ans;
	usint res;
	scanf("%d\n",&T);
	while(T--)
	{
		Ans=0;
		scanf("%d %d\n",&N,&M);
		for(usint i=1;i<=N;i++)
		{
			res=gcd(i,N);
			if(res>=M) Ans++;
		}
		printf("%d\n",Ans);
	}
	return 0;
}