#include <fstream>
#include <string>
#define maxSize 100000000/16+1
using namespace std;
unsigned long long nr_div_prim(unsigned long long n)
{
	unsigned long long d = 2, p, nr = 0;
	while (n > 1) {
		p = 0;
		while (!(n % d)) { n /= d; ++p; }
		if (p > 0) ++nr;
		++d;
		if (n > 1 && d * d > n) d = n;
	}
	return nr;
}
void eratostene(unsigned long long n,char p[]);
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
	unsigned long long T, n, k,i; bool gasit;
	char* p = new char[maxSize];
	f >> T;
	while (T--) {
		f >> n >> k;
		eratostene(n,p);
		gasit = false;
		for (i = (unsigned long long)strlen(p)+1; i > 1 && gasit==false; --i)
			if ((p[i] - '0') == k) {
				g << p[i] << endl;
				gasit == true;
			}
		if (gasit == false) g << 0 << endl;
	}
	f.close(); g.close();
}
void eratostene(unsigned long long n, char p[]) {
	unsigned long long i, j;
	for (i = 1; ((i * i) << 1) + (i << 1) <= n; ++i) {
		if (!(p[i >> 3] & (1 << (i & 7)))) {
			for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {
				p[j >> 3] |= (1 << (j & 7));
			}
		}
	}
	for (i = (unsigned long long)strlen(p)+1; i > 0; --i) p[i] = nr_div_prim(i);
}