#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;

vector<bool> ciur;
vector<int> primeNos;
vector<bool> numere;

void mark(long long i, long long n)
{
	int j = i;
	while(j<=n)
	{
		ciur[j] = 0;
		j += i;
	}
}

void initialize_ciur()
{
	for(int i=0;i<ciur.size();i++)
		ciur[i] = 1;
}


void gen_ciur(long long n,long long a)
{
	ciur.resize(a+5,1);
	initialize_ciur();
	long long i=2;
	
	while(i<=n)
	{	
		if(ciur[i] && n%i == 0)
			mark(i,a);
		++i;
	}
}



void compute()
{
	long long a,b;
	scanf("%llu %llu",&a,&b);
	gen_ciur(b,a);
	long long count = 0;
	for(int i=1;i<=a;i++)
		count += ciur[i];
			
	printf("%llu\n",count);
	

}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		compute();
}