题目大意是给定 $n$，$k$，求 $a^{k}-b^{k}=n$ 的正整数解的个数，$n<=10^{18}$，$k<=64$。

代码不知道为啥超时了，只是把 $long$ $long$ 的快速幂改了一下。

#include<bits/stdc++.h>
#define INF 2e18
using namespace std;
typedef __int128 ll;
ll n,k,nP;
vector<ll> pe;
inline ll read(){
	ll res=0;
	char scan[1005];
	scanf("%s",scan);
	for(int i=0;i<strlen(scan);i++)
		res*=10,res+=scan[i]-'0';
	return res;
}
inline void print(ll num){
	if(num>9) 
		print(num/10);
	putchar(num%10+'0');
}
ll qp(ll x,ll p){
	ll res=1;
	while(p){
		if(p%2==1) res=res*x;
		x=x*x;
		p/=2;
	}
	return res;
}
void input(){
	n=read(); k=read();
}
void solveBF(){
	pe.clear(); nP=0;
	ll l=1,r=n,mx=0;
	while(l<=r){
		ll mid=(l+r)/2;
		if(qp(mid,k-1)<=n){
			mx=mid;
			l=mid+1;
		}else r=mid-1;
	}
	ll cnt=0;
	for(ll i=1;i<=mx;i++)
		if(n%i==0){
			nP++;
			pe.push_back(i);
		}
	for(ll b=1;b<=mx;b++){
		ll val=qp(b,k);
		if(val==INF) val=0;
		ll l=0,r=nP-1,a=0;
		while(l<=r){
			ll mid=(l+r)/2;
			if(qp(b+pe[mid],k)<=n+val){
				a=b+pe[mid];
				l=mid+1;
			}else r=mid-1;
		}
//		printf("%lld %lld\n",a,b);
		if(qp(a,k)==n+val) cnt++;//,printf("%lld %lld\n",a,b);
	}
	print(cnt);
	printf("\n");
}
void solve(){
	ll cnt=0;
	for(ll x=1;x*x*x<=n;x++){
		if(n%x!=0) continue;
		ll l=1,r=__int128(1e9),b=0;
		while(l<=r){
			ll mid=(l+r)/2;
			if((mid+x)*(mid+x)*(mid+x)-mid*mid*mid<=n){
				b=mid;
				l=mid+1;
			}else r=mid-1;
		}
		if((b+x)*(b+x)*(b+x)-b*b*b==n) cnt++;
	}
	print(cnt);
	printf("\n");
}
int main(){
	ll T;
	T=read(); 
	for(ll i=1;i<=T;i++){
		input();
		if(k==3)
			solve();
		else
			solveBF();
	} 
	return 0;
}