#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <set>
#include <cmath>
#include <vector>
#include <map>
#include <cassert>
#define space ' '
#define endl '\n'
#define de(x) cout<<"** "<<x<<" **"<<endl;
#define N 200005
using namespace std;
using ll=long long;
using rr=__int128;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double eps=1e-6;

rr ppow(rr a,rr b){
    rr res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getsqrt(ll t){
    int nd=pow(t,0.5);
    for(int i=max(0,nd-3);i<=nd+3;i++){
        if(1ll*i*i==t)return i;
    }
    // assert(0);
    return -1;
}
rr nd[660005];
signed main(){
    #ifdef LOCAL
        freopen("D:\\code2023\\test\\input.txt", "r", stdin);
        freopen("D:\\code2023\\test\\output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;

    while(T--){
        ll n,k;
        cin>>n>>k;
        int cnt=0;
        if(k>=4){
            for(int i=1;i<660005;i++){
                nd[i]=ppow(i,k-1);
            }
            for(int b=1;b<=3.3*1e5;b++){
                rr tmp=nd[b];
                // if(tmp>n)break;
                if(k*tmp>n)break;
                rr now=n+tmp*b;
                int tmpa=pow(now,1.0/k);
                // cout<<b<<space<<now<<space<<tmpa<<endl;
                // de()
                for(int i=max(b,tmpa-5);i<=tmpa+5;i++){
                    // de(3)
                    if(nd[i]*i==now){
                        cnt++;
                        break;
                    }
                }
            }
        }else{
            for(ll t=1;t<=1e6;t++){
                if(n%t!=0)continue;
                ll s=n/t;
                if(t*t>=s)break;
                ll ab3=s-t*t;
                if(ab3<=0)break;
                if(ab3%3!=0)continue;
                ll ab=ab3/3;
                ll ajb2=t*t+4*ab;
                ll ajb=getsqrt(ajb2);
                if(ajb==-1)continue;
                ll a=ajb+t;
                ll b=ajb-t;
                if(a&1)continue;
                if(b&1)continue;
                a/=2;
                b/=2;
                // if(a*a*a-b*b*b==n)
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }

    return 0;
}