#include <bits/stdc++.h>
#define int long long
using namespace std;
__int128 ksm(__int128 x, int y)
{
    __int128 ans = 1;
    while (y)
    {
        if (y & 1) ans *= x;
        x *= x, y >>= 1;
    }
    return ans;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    if (k == 3)
    {
        int ans = 0;
        for (int i = 1; i <= 1e6; i++)
        {
            if (n % i) continue;
            int tmp = n / i - i * i;
            if (tmp % 3) continue;
            tmp /= 3;
            int delta = i * i + 4 * tmp;
            if (delta < 0) continue;
            int os = (int) sqrt(delta);
            if (os * os != delta) continue;
            int x = i + os;
            if (x & 1) continue;
            x /= 2;
            if (x > i) ans++;
        }
        cout << ans << '\n';
    }
    else
    {
        __int128 sum = 1;
        int ans = 0;
        for (int i = 1; sum <= 1e24; i++)
        {
            int tmp = floor(pow(sum - n, 1.0 / k));
            if (sum - ksm(tmp, k) == n)
                ans++;
            sum = ksm(i, k);
        }
        cout << ans << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}