#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

u64 mul(u64 a, u64 b, u64 M) {
    i64 r = a * b - M * u64(1.L / M * a * b);
    return r + M * ((r < 0) - (r >= (i64)M));
}
u64 power(u64 a, u64 b, u64 M) {
    u64 r = 1;
    for (; b; b /= 2, a = mul(a, a, M))
        if (b & 1) r = mul(r, a, M);
    return r;
}
bool isPrime(u64 n) {
    if (n < 2 or n % 6 % 4 != 1) return (n | 1) == 3;
    auto magic = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    u64 s = __builtin_ctzll(n - 1), d = n >> s;
    for (u64 x : magic) {
        u64 p = power(x % n, d, n), i = s;
        while (p != 1 and p != n - 1 and x % n and i--) {
            p = mul(p, p, n);
        }
        if (p != n - 1 and i != s) return 0;
    }
    return 1;
}
u64 pollard(u64 n) {
    u64 c = 1;
    auto f = [&](u64 x) { return mul(x, x, n) + c; };
    u64 x = 0, y = 0, p = 2, q, t = 0;
    while (t++ % 128 or gcd(p, n) == 1) {
        if (x == y) c++, y = f(x = 2);
        if (q = mul(p, x > y ? x - y : y - x, n)) p = q;
        x = f(x), y = f(f(y));
    }
    return gcd(p, n);
}
u64 primeFactor(u64 n) {
    return isPrime(n) ? n : primeFactor(pollard(n));
}

void solve() {
    i64 n, k;
    cin >> n >> k;

    vector<pair<i64, i64>> divs;
    {
        i64 x = n;
        while (x > 1) {
            i64 p = primeFactor(x);
            int c = 0;
            while (x % p == 0) {
                x /= p;
                c++;
            }
            divs.push_back({p, c});
        }
    }

    auto check = [&](i64 d) -> bool {
        const i64 t = n / d;
        auto cal = [&](i64 x) -> i64 {
            i64 s = 1;
            for (int i = 1; i <= k - 1; i++) {
                if (s > t / (x + d)) {
                    return t + 1;
                }
                s *= (x + d);
            }
            i64 cur = 0;
            for (int i = k - 1; i >= 0; i--) {
                cur += s;
                if (cur > t) {
                    return t + 1;
                }
                if (s != 1) {
                    s /= (x + d);
                    s *= x;
                }
            }
            return cur;
        };

        const i64 L = 1E9 + 10;
        i64 x = *ranges::partition_point(views::iota(1LL, L),
                [&](i64 x) {
                    return cal(x) < t;
                });
        // if (cal(x) == t) cerr << "a = " << d + x << " b = " << x << '\n';
        return cal(x) == t;
    };

    i64 ans = 0;
    auto dfs = [&](auto &&self, i64 x, int i) -> void {
        if (i == divs.size()) {
            ans += check(x);
            return;
        }
        auto [p, c] = divs[i];
        for (int j = 0; j <= c; j++) {
            self(self, x, i + 1);
            x *= p;
        }
    };
    dfs(dfs, 1, 0);

    cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}