#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    using T = __int128;
    const ll inf = (ll)1e18 + 10;

    vector<vector<ll>> v(65);
    vector<vector<T>> vv(65);
    set<T> st[65];

    for (int i = 3; i < 64; ++i) {
        v[i].push_back(0);
        for (ll j = 1;; ++j) {
            ll p = 1;
            bool ok = true;
            for (int k = 0; k < i; ++k) {
                if (p > inf / j) {
                    ok = false;
                    break;
                }
                p *= j;
            }
            if (ok) {
                v[i].push_back(p);
                vv[i+1].push_back((T)p*j);
                st[i+1].insert(vv[i+1].back());
            } else {
                break;
            }
        }
    }

    int qq; cin >> qq;
    while (qq--) {
        ll n,k; cin >> n >> k;
        ll res = 0;
        if (k >= 4) {
            for (int i = 1; i < v[k-1].size(); ++i) {
                T a = vv[k][i];
                a -= n;
                if (st[k].find(a) != st[k].end()) res += 1;
            }
        }
        else {
            for (ll i = 1; i*i*i <= n; ++i) {
                if (n%i) continue;
                ll p = i, q = n/i;
                // a-b = p, a^2 + ab + b^2 = q
                // (p+b)^2 + (p+b)b + b^2 = q
                // 3b^2 + 3pb + (p^2-q) = 0
                ll d = p*p-q;
                if (d%3) continue;
                d /= 3;
                // b^2 + pb + d = 0
                long double X = (-p + sqrt(p*p - 4*d));
                X /= 2.0;
                ll x = round(X);
                if (x*x + p*x + d == 0) res += 1;
            }
        }
        cout << res << "\n";
    }
}