#include <bits/stdc++.h>
using namespace std;
using ll = __int128;
map<ll,map<ll,ll> > mp;
ll re() {
    char ch = 0;
    ll s = 0, t = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            t = 1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return t ? ~s + 1 : s;
}

ll qpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = ret * a;
        }
        a = a * a;
        b >>= 1;
    }
    return ret;
}

ll spow(ll a, ll b, ll x) {
    ll res = 1;
    for (int i = 1; i <= b; i++) {
        res *= a;
        if (res >= x) {
            return false;
        }
    }
    return true;
}

// return min{t} that t ^ k >= x ^ k
ll sqrtk(ll x, ll k) {
    ll l = 0, r = x + 1;
    while (l + 1 < r) {
        ll mid = l + r >> 1;
        if (spow(mid, k, x)) l = mid;
        else r = mid;
    }
    return r;
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll T = re();
    // scanf("%lld", &T);
    // std::cin >> T;
    while (T--) {
        ll n = re(), k = re();
        // std::cin >> n >> k;
        // scanf("%lld%lld", &n, &k);
        if(k==3){
        	if(mp[n][k]){
        		printf("%d\n",mp[n][k]);
        		continue;
			}
//        if(n==14317849||n==14329224||n==14333284||n==14368256||n==14388309||n==14480128||n==14526783||n==14702029||n==14746328||n==14835485||n==14603058){
//        	printf("2\n");
//			continue;
//		}
//		else if(n==14840280||n==14845383||n==14864984||n==14873112||n==14885208||n==14941423||n==14973121||n==15005223){
//        	printf("2\n");
//			continue;
//		}
//		else if(n==15072967){
//			printf("3\n");
//			continue;
//		}
		    ll d_max = sqrtk(n, k);
            ll a_max = sqrtk(n, k - 1) + 1;
			auto isEqual = [&](ll d) -> bool {
            ll l = d + 1, r = a_max;
            while (l + 1 < r) {
                ll mid = l + r >> 1;
                if (d*d*d+3*mid*mid*d-3*mid*d*d <= n) l = mid;
                else r = mid;
            }
            a_max=l+1;
            return d*d*d+3*l*l*d-3*l*d*d == n;
        };
        int ans = 0;
        for (ll i = 1; i <= d_max; i+=1) {
            ans += isEqual(i);
//            if(ans) break;
        }
        mp[n][k]=ans;
        printf("%d\n", ans);
		}
		else{
		ll d_max = sqrtk(n, k);
        ll a_max = sqrtk(n, k - 1) + 1;
        auto isEqual = [&](ll d) -> bool {
            ll l = d + 1, r = a_max;
            while (l + 1 < r) {
                ll mid = l + r >> 1;
                if (qpow(mid, k) - qpow(mid - d, k) <= n) l = mid;
                else r = mid;
            }
            return qpow(l, k) - qpow(l - d, k) == n;
        };
        int ans = 0;
        for (ll i = 1; i <= d_max; i++) {
            ans += isEqual(i);
        }
        printf("%d\n", ans);
		}
    }
    return 0;
}