#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
long long gcd(long long a,long long b)
{
	while(b^=a^=b^=a%=b);
	return a;
}
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	long long n;
	long long a=0,b=0,s=0;
	scanf("%d",&n);
	for(long long i=0;i<n;i++)
	{
		s=0;
		scanf("%lld%lld",&a,&b);
		for(long long j=1;j<=a;j++)
		{
			if(gcd(j,a)>=b)
				s++;
		}
		printf("%lld\n",s);
	}
	return 0;
}