#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
ll n,k,sum;
queue<ll> s;
int cz(int i)
{
	queue<ll> a=s;
	while(!a.empty())
	{
		if(a.front()==i)
		{
			return 0;
		}
		a.pop();
	}
	return 1;
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		if(k==0)
		{
			cout<<1<<endl;
			continue;
		}
		for(ll i=(n/(k+1));i<n/k;i++)
		{
			if(s.empty()) s.push(n%i);
			else
			{
				if(cz(n%i))
				{
					s.push(n%i);
				}
			}
		}
		cout<<s.size()<<endl;
	}
	return 0;
}