#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using i64 = long long;
using i128 = __int128;
i64 mul(i64 a, i64 b, i64 m) {
	return static_cast<__int128> (a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
	i64 res = 1 % m;
	for (; b; b >>= 1, a = mul(a, a, m))
		if (b & 1) res = mul(res, a, m);
	return res;
}
bool isprime(i64 n) {
	if (n < 2) 
		return false;
	static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
	int s = __builtin_ctzll(n - 1);
	i64 d = (n - 1) >> s;
	for (auto a : A) {
		if (a == n)
			return true;
		i64 x = power(a, d, n);
		if (x == 1 || x == n - 1)
			continue;
		bool ok = false;
		for (int i = 0; i < s - 1; ++i) {
			x = mul(x, x, n);
			if (x == n - 1) {
				ok = true;
				break;
			}
		}
		if (!ok)
			return false;
	}
	return true;
}

vector<i64> factorize(i64 n) {
	vector<i64> p;
	function<void(i64)> f = [&] (i64 n) {
		if (n <= 10000) {
			for (int i = 2; i * i <= n; ++i)
				for (; n % i == 0; n /= i)
					p.push_back(i);
			if (n > 1)
				p.push_back(n);
			return ;
		}
		if (isprime(n)) {
			p.push_back(n);
			return;
		}
		auto g = [&] (i64 x) {
			return (mul(x, x, n) + 1) % n;
		};
		i64 x0 = 2;
		while (true) {
			i64 x = x0;
			i64 y = x0;
			i64 d = 1;
			i64 power = 1, lam = 0;
			i64 v = 1;
			while (d == 1) {
				y = g(y);
				++lam;
				v = mul(v, std::abs(x - y), n);
				if (lam % 127 == 0) {
					d = std::__gcd(v, n);
					v = 1;
				}
				if (power == lam) {
					x = y;
					power *= 2;
					lam = 0;
					d = std::__gcd(v, n);
					v = 1;
				}
			}
			if (d != n) {
				f(d);
				f(n / d);
				return ;
			}
			++x0;
		}
	};
	f(n);
	sort(p.begin(), p.end());
	return p;
}
void solve(){
	i64 n, k;
	cin >> n >> k;
	
	auto qpow = [&] (i128 a, i128 b) -> i128 {
		i128 res = 1;
		while (b) {
			if (b & 1) res = res * a;
			a = a * a;
			b >>= 1;
		}
		return res;
	};
	
	if (k >= 6) {
		int ans = 0;
		int MAXN = max(pow(n / k + 1, 1.0 / (k - 1)) + 1, 2.1);
		for (i64 b = 1; b <= MAXN; b++) {
			i128 a = pow(qpow(b, k) + n, 1.0 / k);
			if (qpow(a, k) - qpow(b, k) == n) {
				ans++;
			}
		};
		cout << ans << '\n';
		
		return ;
	}
	
	vector<i64> pf = factorize(n), fact;
	
	auto dfs = [&] (auto self, i64 d, int i) -> void {
		if (i == pf.size()) {
			fact.push_back(d);
			return ;
		}
		int j = i;
		while (j < pf.size() && pf[j] == pf[i]) j++;
		for (int cnt = 0; cnt <= j - i; cnt++) {
			self(self, d, j);
			d *= pf[i];
		}
	};
	
	dfs(dfs, 1, 0);
	
//	for (auto x : fact) {
//		cout << x << ' ' ;
//	}
//	cout << '\n' << fact.size() << '\n';
	
	// (b + d) ^ k - b ^ k = n
	// k * b ^ (k - 1) * d > n
	// b = pow(n / (k * d), 1 / (k - 1)))
	
	int ans = 0;
	
	for (i64 d : fact) {
		if (k == 3) {
			i128 delta = (i128)12 * n / d - 3 * (i128)d * d;
			i64 b = (-3 * d + sqrtl(delta)) / 6, a = b + d;
			if (b > 0 && a * a + a * b + b * b == n / d) ans++;
			continue;
		}
		
		i64 l = 2, r = max(pow(n / (i128)(k * d) + 1, 1.0 / (k - 1)) + 1, 2.1);
		
		auto check = [&] (i64 mid) -> int {
			i128 a = 1, b = 1;
			int cnt = 0;
			while (a - b <= n && cnt <= k + 2) {
				a = a * (mid + d);
				b = b * mid;
				cnt++;
			}
			return cnt - 1;
		};
		
		while (l != r) {
			i64 mid = l + r >> 1;
			if (k <= check(mid)) l = mid + 1;
			else r = mid;
		}
		l--;
		if (qpow(l + d, k) - qpow(l, k) == n) {
			ans++;
		}
	}
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}