#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

using i128 =__int128;
ll power(ll a, ll b, ll m) {
    ll res = 1;
    for (; b; b >>= 1, a = i128(a) * a % m) {
        if (b & 1) {
            res = i128(res) * a % m;
        }
    }
    return res;
}
  
bool isprime(ll p) {
    if (p < 2) {
        return 0;
    }
    ll d = p - 1, r = 0;
    while (!(d & 1)) {
        r++;
        d >>= 1;
    }
    int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (auto a : prime) {
        if (p == a) {
            return true;
        }
        ll x = power(a, d, p);
        if (x == 1 || x == p - 1) {
            continue;
        }
        for (int i = 0; i < r - 1; i++) {
            x = i128(x) * x % p;
            if (x == p - 1) {
                break;
            }
        }
        if (x != p - 1) {
            return false;
        }
    }
    return true;
}
  
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
  
ll pollard_rho(ll x) {
    ll s = 0, t = 0;
    ll c = (ll)(rng()) % (x - 1) + 1;
    ll val = 1;
    for (int goal = 1; ; goal <<= 1, s = t, val = 1) {
        for (int step = 1; step <= goal; step++) {
            t = (i128(t) * t + c) % x;
            val = i128(val) * abs(t - s) % x;
            if (step % 127 == 0) {
                ll g = __gcd(val, x);
                if (g > 1) {
                    return g;
                }
            }
        }
        ll g = __gcd(val, x);
        if (g > 1) {
            return g;
        }
    }
}
 
unordered_map<ll, int> getprimes(ll x) {
    unordered_map<ll, int> p;
    function<void(ll)> get = [&](ll x) {
        if (x < 2) {
            return;
        }
        if (isprime(x)) {
            p[x]++;
            return;
        }
        ll mx = pollard_rho(x);
        get(x / mx);
        get(mx);
    };
    get(x);
    return p;
}
  
vector<ll> getfac(ll x) {
    vector<ll> fac;
    auto primes = getprimes(x);
    vector<pair<ll, int>> tmp(primes.begin(), primes.end());
    int SIZE = tmp.size();
    function<void(int, ll)> dfs = [&](int id, ll x) {
        if (id == SIZE) {
            fac.push_back(x);
            return;
        }
        ll p = 1;
        for (int i = 0; i <= tmp[id].second; i++) {
            if (i != 0) {
                p *= tmp[id].first;
            }
            dfs(id + 1, x * p);
        }
    };
    dfs(0, 1);
    return fac;
}

void solve() {
	
	ll n , k;
	cin >> n >> k;
	
	auto check = [&](ll a , ll b){
		__int128 A = 1 , B = 1;
		for(int i = 0 ; i < k ; i++){
			A *= a , B *= b;
			if(A - B >= n) return true;
		}
		return false;
	};
	
	auto check1 = [&](ll a , ll b){
		
		ll A = 1 , B = 1;
		for(int i = 0 ; i < k ; i++){
			A *= a , B *= b;
			if(A - B > n) return false;
		}
		//cout << A <<' ' << B << '\n';
		return (A - B) == n;
	};
		
	ll cnt = 0;
	auto e = getfac(n);
	// for(auto t : e) cout << t << ' ';
	// cout << '\n';
	for(auto t : e){
		ll le = 1 , ri = 1e9 , ans = -1;
		while(le <= ri){
			ll mid = (le + ri) >> 1;
			ll b = mid , a = t + mid;
			if(check(a , b)){
				ri = mid - 1; ans = mid;
			}
			else le = mid + 1;
		}
		//cout << ans << '\n';
		if(ans == -1) continue;
		if(check1(ans + t , ans)) cnt++;
	}
	
	cout << cnt << '\n';
	//cout << '\n';
    
}

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