#include<bits/stdc++.h>

using namespace std;
using i32 = int;
using ll = __int128;
#define int long long


const int N = 1000;
int cntp;        //质数的个数
int prime[168];   //从0开始
int vis[N];     //存最小质因数
void euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = i;
            prime[cntp++] = i;
        }
        for (int j = 0; j < cntp; j++) {
            if (i * prime[j] > n) break;
            vis[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}

int mul(int a, int b, int m) {
    int r = a * b - m * (int) (1.L / m * a * b);
    return r - m * (r >= m) + m * (r < 0);
}

int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

bool isPrime(int n) {
    if (n <= 1) return 0;
    for (int p: B) {
        if (n == p) return 1;
        if (n % p == 0) return 0;
    }
    auto mypow = [](int a, int n, int m) -> int {
        int res = 1;
        while (n) {
            if (n & 1) res = mul(res, a, m);
            a = mul(a, a, m);
            n >>= 1;
        }
        return res;
    };

    int m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p: B) {
        int t = m, a = mypow(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1) {
            a = mul(a, a, n);
            t *= 2;
        }
        if (a != n - 1 && t % 2 == 0) return 0;
    }
    return 1;
}

int pollard_rho(int n) {
    for (int p: B) {
        if (n % p == 0) return p;
    }
    auto f = [&](int x) -> int {
        x = mul(x, x, n) + 1;
        return x >= n ? x - n : x;
    };
    int x = 0, y = 0, tot = 0, p = 1, q, g;
    for (int i = 0; (i & 255) || (g = gcd(p, n)) == 1; i++, x = f(x), y = f(f(y))) {
        if (x == y) {
            x = tot++;
            y = f(x);
        }
        q = mul(p, abs(x - y), n);
        if (q) p = q;
    }
    return g;
}

unordered_map<int, int> factor(int n) {
    unordered_map<int, int> ans;
    vector<int> stk;
    for (auto p: prime) {
        while (n % p == 0) {
            ans[p]++;
            n /= p;
        }
    }
    if (n == 1) return ans;
    stk.push_back(n);
    while (!stk.empty()) {
        int b = stk.back();
        stk.pop_back();
        if (isPrime(b)) {
            ans[b]++;
            continue;
        }
        int c = b;
        while (c >= b) c = pollard_rho(b);
        stk.push_back(c);
        stk.push_back(b / c);
    }
    return ans;
}

vector<int> divisors_by_pf(unordered_map<int, int> &pf) {
    vector<int> div = {1};
    for (auto &&[p, e]: pf) {
        int n = div.size();
        int pp = 1;
        for (int i = 1; i <= e; i++) {
            pp *= p;
            for (int j = 0; j < n; j++) div.push_back(div[j] * pp);
        }
    }
    return div;
}

//分解因数
vector<int> divisors(int n) {
    auto pf = factor(n); //分解质因数
    return divisors_by_pf(pf);
}

ll power(ll a, int n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    auto check = [&](int dt, int b) -> bool {
        return power(dt + b, k) - power(b, k) <= n;
    };
    int ans = 0;
    vector<int> div = divisors(n);
    for (int dt: div) {
        int l = 1, r = (int) pow(n / dt, 1.0 / (k - 1));
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(dt, mid)) l = mid;
            else r = mid;
        }
        if (power(dt + l, k) - power(l, k) == n) ans++;
    }
    cout << ans << "\n";
}

signed main() {
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int Tcase = 1;
    ios::sync_with_stdio(0), cin.tie(0);
    euler(1000);
    cin >> Tcase;
    while (Tcase--) {
        solve();
    }
    return 0;
}