#pragma GCC optimize "Ofast"
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ull = unsigned long long;
ull inf = 1e19;

const inline ull pow3(ull n) {
	if (n*n >= (inf/n)) return inf;
	return n*n*n;
}
const inline ull pow4(ull n) {
	if (n*n >= (inf/(n*n))) return inf;
	ull a = (n*n);
	return a*a;
}
const inline ull pow(ull n, ull p) {
	if (p == 2) return n*n;
	else if (p == 3) return pow3(n);
	else if (p == 4) return pow4(n);
	ull out = 1;
	while (p-- > 0) {
		if (out >= inf/n) return inf;
		out *= n;
	}
	return out;
}

void solve(ull n, ull k) {
	if (k >= 63) {
		cout << 0 << endl;
		return;
	}
	ull rootk = 1, rootk1 = 1;
	for (int i = 0; i < 200; i++) {
		rootk = (rootk+(n/pow(rootk, k-1)))/2;
		rootk1 = (rootk1+(n/pow(rootk1, k-2)))/2;
	}
	rootk++;
	rootk1++;
	while(pow(rootk-1, k) >= n)rootk--;
	while(pow(rootk1-1, k-1) >= n)rootk1--;
	assert(pow(rootk, k) >= n);
	assert(pow(rootk1, k-1) >= n);
	assert(pow(rootk-1, k) < n);
	assert(pow(rootk1-1, k-1) < n);
	ull out = 0;
	for (ull c = 1; c <= rootk; c++) {
		if (n%c != 0) continue;
		ull lb = 1, ub = rootk1;
		while (lb < ub-1) {
			ull m = (lb+ub)/2;
			ull val = pow(m+c, k);
			if (val == inf) {
				ub = m;
				continue;
			}
			val -= pow(m, k);
			if (val > n) ub = m;
			else if (val <= n) lb = m;
		}
		if (pow(lb+c, k) - pow(lb, k) == n) {
			out++;
		}
	}
	cout << out << endl;
}

int main() {
	int t; cin >> t;
	while (t--) {
		ull n, k; cin >> n >> k;
		solve(n, k);
	}
}