#include<bits/stdc++.h>
using namespace std;
#define ll long long
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;
}
ll n,k;
int fun(ll a,ll b)
{
	i128 s1=1,s2=1;
	int t=k;
	while(t--)
	{
		s1*=a;
		s2*=b;
		if(s1-s2>=n)return 1;
	}
	return 0;
}
int fun2(ll a,ll b)
{
	i128 s1=1,s2=1;
	int t=k;
	while(t--)
	{
		s1*=a;
		s2*=b;
		if(s1-s2>n)return 0;
	}
	//cout<<a<<' '<<b<<' '<<s1<<' '<<s2<<'\n';
	return s1-s2==n;
}
int check(ll x)
{
	ll l=1,r=1e18,ans=-1;
	while(l<=r)
	{
		ll mid=(l+r)/2;
		if(fun(mid+x,mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
		l=mid+1;
	}
	if(ans==-1)return 0;
	//cout<<x<<' '<<ans<<'\n';
	return fun2(ans+x,ans);
}
void solve(){
   
    cin>>n>>k;
    auto e=getfac(n);
    int ans=0;
    for(auto x:e)
    {
    	if(check(x))ans++;
    }
    cout<<ans<<'\n';
}

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