#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ar array
#define ll long long
typedef int uci;
#define int long long
#define all(x) begin(x), end(x)

// from kactl
typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}
bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}
ull pollard(ull n) {
	auto f = [n](ull x) { return modmul(x, x, n) + 1; };
	ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}
vector<ull> factor(ull n) {
	if (n == 1) return {};
	if (isPrime(n)) return {n};
	ull x = pollard(n);
	auto l = factor(x), r = factor(n / x);
	l.insert(l.end(), all(r));
	return l;
}
// end from
int calc(int x, int b, int lim, int k){
    int a = x+b;
    int out{};
    
    int m = 1;
    for(int i{}; i < k-1; ++i){
        int li = lim/m;
        if(li < a){
            return -1;
        }
        m *= a;
    }

    out = m;
    for(int i{1}; i <= k-1; ++i){
        m /= a;
        int li = (lim-out)/m;
        if(li < b){
            return -1;
        }
        m *= b;
        out += m;
    }
    return out;
}

void solve(){
    ull n;
    cin >> n;
    int k;
    cin >> k;
    vector<ull> fa = factor(n);
    sort(fa.begin(), fa.end());

    vector<int> vals{1};
    for(int i{}; i < fa.size();){
        int j = i;
        while(j < fa.size() && fa[j] == fa[i])
            j++;

        int amt = j-i;
        int si = vals.size();
        int mult = fa[i];
        for(int j{}; j < amt; ++j){
            for(int o{}; o < si; ++o)
                vals.push_back(vals[o]*mult);
            mult *= fa[i];
        }

        i = j;
    }

    int out{};
    for(int i : vals){
        int lim = n/i;
        int l = 1, r = lim;
        int ans = -1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(calc(i, mid, lim, k) == -1)
                r = mid-1;
            else{
                ans = mid;
                l = mid+1;
            }
        }

        if(ans != -1 && calc(i, ans, lim, k) == lim)
            out++;
    }
    cout << out << '\n';
}

uci main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
}