#include <bits/stdc++.h>
#define int long long
using namespace std;
using i64 = long long;

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;
}
std::vector<i64> factorize(i64 n) {
    std::vector<i64> p;
    std::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);
    std::sort(p.begin(), p.end());
    return p;
}

vector<i64> get_divisors(i64 n) {
    vector<i64> p = factorize(n);
    vector<int> pw(p.size());
    for (int i = 0;i < p.size();i ++ ) {
        while (n && n % p[i] == 0) 
            n /= p[i], ++ pw[i];
    }
    vector<i64> ans;
    auto dfs = [&](auto&& self, int u, i64 d) -> void {
        if (u == p.size()) {
            ans.push_back(d);
        } else {
            i64 cur = d;
            self(self, u + 1, cur);
            for (int i = 0;i < pw[u];i ++ ) {
                cur *= p[u];
                self(self, u + 1, cur);
            }
        }
    };dfs(dfs, 0, 1);
    return ans;
}

void sol() {
    i64 N;int K;
    cin >> N >> K;
    vector<i64> d = get_divisors(N);

    const i64 U = 2e18;
    auto safe_pow = [&](i64 x, int k) -> i64 {
        i64 ans = 1;
        for (int i = 0;i < k;i ++ ) {
            i64 tmp;
            if (__builtin_mul_overflow(ans, x, &tmp)) {
                return U;
            }
            ans *= x;
        }
        return ans;
    };

    auto calc = [&](i64 x, i64 y) -> i64 {
        i64 ans = 0;
        for (int i = 0;i < K;i ++ ) {
            i64 u1 = safe_pow(x, K - i - 1);
            i64 u2 = safe_pow(y, i);
            if (u1 == U || u2 == U)
                return U;
            i64 tmp;
            if (__builtin_mul_overflow(u1, u2, &tmp))
                return U;
            ans += u1 * u2;
            if (ans >= U) 
                return U;
        }
        return ans;
    };
    int res = 0;
    for (auto x : d) {
        int l = 1, r = 1e9;
        while (l < r) {
            int mid = l + r >> 1;
            if (__int128_t(calc(mid, mid + x)) * x >= N) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (__int128_t(calc(l, l + x)) * x == N)
            ++ res;
    }
    cout << res << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t;cin >> t;
    while (t -- ) {
        sol();
    }
}