#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#pragma GCC optimize(2)
typedef long long ll;
using namespace std;

struct Factor{
    using i64=long long;
    using f64=long double;
    i64 p{};
    f64 invp{};
    void setmod(i64 x){
        p=x,invp=(f64)1/x;
    }
    i64 mul(i64 a,i64 b){
        i64 z=a*invp*b+0.5;
        i64 res=a*b-z*p;
        return res+(res>>63&p);
    }
    i64 pow(i64 a,i64 x,i64 res=1){
        for(;x;x>>=1,a=mul(a,a))
            if(x&1) res=mul(res,a);
        return res;
    }
    vector<int> p1{2,7,61};
    vector<int> p2{2,325,9375,28178,450775,9780504,1795265022};
    vector<int> test_p;
    bool checkprime(i64 p){
        if(p==1) return 0;
        if(p<1ll<<32) test_p=p1;
        else test_p=p2;
        setmod(p);
        i64 d=__builtin_ctzll(p-1),s=(p-1)>>d;
        for(i64 a:test_p){
            if(a%p==0) continue;
            i64 x=pow(a,s),y;
            for(int i=0;i<d;++i,x=y){
                y=mul(x,x);
                if(y==1 && x!=1 && x!=p-1) return 0;
            }
            if(x!=1) return 0;
        }
        return 1;
    }
    i64 rho(i64 n){
        if(!(n&1)) return 2;
        static std::mt19937_64 gen((size_t)"hehezhou");
        i64 x=0,y=0,prod=1;
        auto f=[&](i64 o){return mul(o,o)+1;};
        setmod(n);
        for(int t=30,z=0;t%64 || std::gcd(prod,n)==1;++t){
            if(x==y) x=++z,y=f(x);
            if(i64 q=mul(prod,x+n-y)) prod=q;
            x=f(x),y=f(f(y));
        }
        return std::gcd(prod,n);
    }
    vector<pair<i64,i64>> primes_factor(i64 x){
        std::vector<i64> res;
        auto f=[&](auto f,i64 x){
            if(x==1) return;
            if(checkprime(x)) return res.push_back(x);
            i64 y=rho(x);
            f(f,y),f(f,x/y);
        };
        f(f,x),sort(res.begin(),res.end());
        std::vector<pair<i64,i64>> vt;
        for(auto i:res){
            if(vt.empty() || vt.back().x!=i) vt.emplace_back(i,1);
            else vt.back().y++;
        }
        return vt;
    }
    auto factor(int x){
        if(x==1)
        {
            vector<int> v(1,1);
            return v;
        }
        auto fac=primes_factor(x);
        vector<int> div;
        auto dfs=[&](auto &&self,int p,int i)->void{
            if(i==(int)fac.size()){
                div.push_back(p);
                return;
            }
            int P=1;
            for(int j=0;j<=fac[i].y;j++){
                self(self,p*P,i+1);
                P*=fac[i].x;
            }
        };
        dfs(dfs,1,0);
        return div;
    }
}Fac;

// void solve()
// {
    
// }
typedef __int128 lll;
__int128 ksm(__int128 a,__int128 p)
{
    __int128 res=1;
    while(p)
    {
        if(p%2)
        {
            res=res*a;
        }
        a=a*a;
        p/=2;
    }
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int T;
    T=1;
    //while(T--) solve();
    int t;
    cin>>t;
    while(t--)
    {
        ll ans=0;
        ll n,k;
        cin>>n>>k;
        ll mx=0;
        __int128 p=1e18;
            p*=1e9;
        if(k==3)
        {
            mx=1e9;
        }
        else if(k==4)
        {
            mx=1e7;
        }
        else if(k==5)
        {
            mx=1e5;
        }
        else
        {
            mx=1e4;
            for(ll i=1;i<=1e4;i++)
            {
                __int128 now=1;
                
                for(int j=0;j<k;j++)
                {
                    if(now*i>=p)
                    {
                        mx=i;
                        goto next;
                    }
                    now*=i;
                }
            }
            //mx=1e4;
        }
        next:
        //cout<<mx<<"\n";
        vector<ll> vt=Fac.factor(n);
        vector<ll> vt1;
        // for(int i=0;i<vt.size();i++)
        // {
        //     cout<<vt[i]<<" ";
        // }
        // cout<<"\n";
        for(int i=0;i<vt.size();i++)
        {
            if(vt[i]<=mx)
            {
                vt1.push_back(vt[i]);
                //cout<<vt[i]<<" ";
            }
        }
        //cout<<"\n";
        //ll ans=0;
        for(int i=0;i<vt1.size();i++)
        {
            ll d=vt1[i];
            ll l=vt1[i],r=mx+1;
            
            while(l+1<r)
            {
                __int128 now=(l+r)/2;
                //cout<<(l+r)/2<<" "<<l<<" "<<r<<"\n";
                __int128 temp=ksm(now,k)-ksm(now-d,k);
                if(temp==n)
                {
                    ans++;
                    break;
                }
                else if(temp<n)
                {
                    l=now;
                }
                else
                {
                    r=now;
                }
            }
        }
        cout<<ans<<"\n";
        

    }
}