#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
__int128_t INF;
#define B 5e6

void pre()
{
    INF = 0x3fffffffffffffff;
    INF <<= 64;
    INF |= 0xffffffffffffffff;
}

__int128_t qpow(__int128_t a, __int128_t b)
{
    if(a == 0)
        return 0;
    __int128_t ans = 1;
    while (b)
    {
        if(b & 1)
        {
            if(INF / ans <= a)
                return INF;
            ans = ans * a;
        }
        if(INF / a <= a)
            return INF;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<int> divs;
    for (int i = 1; i <= min(sqrt(n), B); i++)
    {
        if(n % i == 0)
        {
            divs.push_back(i);
            if(i * i != n && n / i <= B)
                divs.push_back(n / i);
        }
    }
    int ans = 0;
    for (int x : divs)
    {
        __int128_t l = 1, r = n;
        while (l != r)
        {
            __int128_t mid = (l + r) >> 1;
            if(qpow(mid + x, k) >= INF)
                r = mid;
            else if(qpow(mid + x, k) - qpow(mid, k) >= n)
                r = mid;
            else
                l = mid + 1;
        }
        if(qpow(l + x, k) < INF && qpow(l + x, k) - qpow(l, k) == n)
            ans++;
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    pre();
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}