#include <bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
const int N=2e6+5,B=2e6;
int T,n_,k_;
int128 n,k;

int128 pw(int x,int k){
    int128 tot=1;
    for(int i=1;i<=k;i++) tot*=x;
    return tot;
}
int p[N],id;

signed main(){
    cin>>T;
    while(T--){
        cin>>n_>>k_;
        n=n_,k=k_;
        int ans=0;
        
        id=0;
        
        for(int t=1;pw(t,k-1)<=n && t<=B;t++) p[++id]=pw(t,k);
        int cur=1;
        for(int i=1;i<=id;i++){
            while(cur+1<=id && p[cur]<p[i]+n) cur++;
            if(p[cur]==p[i]+n) ans++;
        }
        
        cout<<ans<<endl;
    }
}