#include<iostream>
#include<fstream>
using namespace std;
unsigned long long g(unsigned long long a,unsigned long long b) 
{
	if(a==0)
	{
		return b;
	}else
	{
		return g(b % a,a);
	}
}
int main()
{
	ifstream fin("gcd.in");
	ofstream fout("gcd.out");
	unsigned long long a,b;
	int i,n,sum;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		sum=0;
		fin>>a>>b;
		for (int j=1;j<=a;j++)
			if (g(j,a)>=b) sum++;
		fout<<sum<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}