#include<bits/stdc++.h>
#define int long long
using namespace std;
__int128 quickpow(__int128 a,int b){
	__int128 ret=1;
	while(b){
		if(b&1) ret=ret*a;
		a=a*a;
		b>>=1;
	}return ret;
}
int prime[1000001],maxn[100001],tot;
bool isprime[100001];
void shai(int n=1e5){
	fill(isprime+1,isprime+1+n,1);
	isprime[1]=0;
	for(int i=2;i<=n;i++){
		if(isprime[i]){
			prime[++tot]=i;
			maxn[i]=i;
		}
		for(int j=1;j<=tot&&prime[j]*i<=n;j++){
			maxn[prime[j]*i]=maxn[i];
			isprime[prime[j]*i]=0;
			if(i%prime[j]==0) break;
		}
	}
}
int mul(int a,int b,int mod){
	int d=a*(long double)b/mod;
	int ret=a*b-d*mod;
	if(ret<0)ret+=mod;
	if(ret>=mod) ret-=mod;
	return ret;
}
int quickpow(int a,int b,int mod){
	int ret=1;
	while(b){
		if(b&1) ret=mul(ret,a,mod)%mod;
		a=mul(a,a,mod)%mod;
		b>>=1;
	}return ret;
}
bool Isprime(int a,int p){
	int d=p-1;
	if(quickpow(a,d,p)!=1) return 0;
	while(!(d&1)){
		d>>=1;
		int t=quickpow(a,d,p);
		if(t==p-1) return 1;
		else if(t!=1) return 0;
	}return 1;
}
int List[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool Mr(int p){
	if(p<=1e5) return isprime[p];
	for(int u:List){
		if(!Isprime(u,p)) return 0;
	}
	return 1;
}
mt19937 rd(time(NULL));
int ran(int l,int r){
	return rd()%(r-l+1)+l;
}
int Pr(int n){
	int x=ran(0,n-1),y=x;
	int c=ran(3,n-1);
	x=(mul(x,x,n)+c)%n;
	y=(mul(y,y,n)+c)%n,y=(mul(y,y,n)+c)%n;
	for(int lim=1;x!=y;lim=min(128ll,lim<<1)){
		int s=1;
		for(int i=0;i<lim;i++){
			int S=mul(s,abs(x-y),n);
			if(!S) break;
			s=S;
			x=(mul(x,x,n)+c)%n;
			y=(mul(y,y,n)+c)%n,y=(mul(y,y,n)+c)%n;
		}
		int d=__gcd(s,n);
		if(d!=1) return d;
	}return n;
}
vector<int> vec;
void solve(int x){
	if(x<=1e5){
		while(x!=1){
			vec.push_back(maxn[x]);
			x/=maxn[x];
		}
		return ;
	}
	if(Mr(x)){
		vec.push_back(x);
		return ;
	}
	int t=Pr(x);
	while(t==x) t=Pr(x);
	solve(t),solve(x/t);
}
int lim=0;
vector<int> ins;
void dfs(int now,int S){
	if(S>lim) return ;
	if(now==vec.size()){
		ins.push_back(S);return ;
	}
	int l=now,r=now;
	while(r+1<vec.size()&&vec[r+1]==vec[l]){
		r++;
	}
	for(int i=0,t=1;i<=r-l+1;i++,t*=vec[l]){
		dfs(r+1,S*t);
	}
}
void solve(){
	vec.clear();ins.clear();
	int n,k;cin>>n>>k;
	lim=pow(n+1,1.0/k);
	while(pow(lim+1,k)<=n+1) lim++;
	while(pow(lim,k)>n+1) lim--;lim--;
	int lim2=pow(n+1,1.0/(k-1));
	while(pow(lim2+1,k-1)<=n+1) lim2++;
	while(pow(lim2,k-1)>n+1) lim2--;lim2--;
	solve(n);
	sort(vec.begin(),vec.end());
	dfs(0,1);
	int ans=0;
//	cout<<lim2<<'\n';
	for(int u:ins){
//		cout<<u<<" ";
		int l=1,r=lim2;
		while(l<=r){
			int mid=(l+r)>>1;
			__int128 C=quickpow(mid+u,k)-quickpow(mid,k);
			if(C==n){
				ans++;break;
			}
			if(C>n){
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
//		if(u==1){
//			l=114429;
//			int C=quickpow(l+u,k)-quickpow(l,k);
//			cout<<l<<" "<<r<<' '<<C<<'\n';
//			592570256192463681
//			592571815933494815
//		}
	}
//	cout<<'\n';
	cout<<min(ans,1ll)<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	shai();
	int tt;cin>>tt;
	while(tt--) solve();
}
/*
1
592570256192463681 4
*/