#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
typedef __int128 i128;
i128 rem[1000000];
int top;
i128 n,k;
i128 qpow(i128 a,i128 b){
    i128 res=1;
    for(;b;a=a*a,b>>=1){
        if(b&1)res=res*a;
    }
    return res;
}
i128 gsqrt(i128 x){
//	printf("x = %lld\n",x);
    i128 _=sqrtl(x);
    while((_+1)*(_+1)<=x)_++;
    while(_*_>x)_--;
    return _;
}
pair<i128,i128> calc(i128 a_minus_b,i128 _3ab){
    i128 delta=9*a_minus_b*a_minus_b+12*_3ab;
    if(delta<0){
        return mkpr(-1,-1);
    }
    delta=gsqrt(delta);
    i128 res1=(-3*a_minus_b+delta)/6;
    i128 res2=(-3*a_minus_b-delta)/6;
    return mkpr(res1,res2);
}
bool chk(i128 a,i128 b,i128 h){
    return ((a-b)*(a*a+a*b+b*b)==h);
}
void solve(int id_of_test){
	read(n);
    read(k);
    if(k==3){
        int lim=pow(n,1.0/3.0);
        lim+=10;
        int ans=0;
	//	printf("lim = %d\n",lim);
        FOR(a_minus_b,1,lim){
		//	puts("??????????????");
	//		printf("%d\n",a_minus_b);
            i128 tmp=n/(a_minus_b);
            i128 _3ab=tmp-(a_minus_b*a_minus_b);
		//	wrintln(tmp);
		//	wrintln(_3ab);
            auto sol_b=calc(a_minus_b,_3ab);
            pair<i128,i128> sol_a;
            sol_a.fi=sol_b.fi+a_minus_b;
            sol_a.se=sol_b.se+a_minus_b;
		//	printf("sol1\n");
		//	wrint(sol_a.fi);
		//	pc(' ');
		//	wrintln(sol_b.fi);
		//	printf("sol2\n");
		//	wrint(sol_a.se);
		//	pc(' ');
		//	wrintln(sol_b.se);
            if(sol_a.fi>0&&sol_b.fi>0){
                if(chk(sol_a.fi,sol_b.fi,n))ans++;
            }
            if(sol_a.se>0&&sol_b.se>0){
                if(chk(sol_a.se,sol_b.se,n))ans++;
            }
        }
        printf("%d\n",ans);
        return;
    }
    i128 base=0;
    while(rem[top]-rem[top-1]<=n){
        rem[++top]=qpow(++base,k);
    }
    int ans=0;
    int lst=1;
    FOR(i,1,top){
        while(rem[i]-rem[lst]>n)lst++;
        ans+=(rem[i]-rem[lst]==n);
    }
    wrintln(ans);
    top=0;
}
int main()
{
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}