#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ll long long
#define int __int128 
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 100+20 , maxm = 2e4 + 220, sq = 500 , inf = 1e9+10 , mod =998244353 ; 
int pw(int x ,int k){
    if(k==3)return x*x*x ; 
    if(k == 0)return 1; 
    int v = pw(x,k/2);
    v = v*v; 
    if(k&1) v = v*x;
    return v ;
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    ll T ;
    cin >> T ;
    while(T--){
        ll n , k ;
        cin >> n >> k ;
        if(k >= 4){
            int x = 1 ; 
            int nw = 1 , ans =0  ;
            while(1){
                while(pw(nw , k)-pw(x, k) > n){
                    x++;
                }
                if(pw(nw , k) - pw(nw-1 , k) > n)break ;
                if(pw(nw, k)-pw(x,k) == n){
                    ans ++ ;
                }
                nw++;
            }
            ll x2 = ans ;
            cout << x2 << "\n"; 
            continue ; 
        }
        int x = 1 ; 
        int nw = 1 , ans =0 , f = 1e5;
        while(1){
            while(pw(nw , k)-pw(x, k) > n){
                x++;
            }
            if(nw >= f && pw(nw , k) - pw(nw-f , k) > n)break ;
            if(pw(nw, k)-pw(x,k) == n && nw - x > f){
                ans ++ ;
            }
            nw++;
        }
        rep(i , 1 , f){
            int l = 0 , r= (1e9+2)/i+2 ; 
            while(r-l > 1){
                int m = (l+r)/2 ;
                int a= i , b= m*m + (m+i)*(m+i) + (m+i)*m ;
                if(b <= n/a){
                    l = m ;
                }else{
                    r = m ;
                }
            }
            int m = l;
            int a= i , b= m*m + (m+i)*(m+i) + (m+i)*m ;
            if(a*b == n){
                ans++ ;
           }
        }
        ll x2= ans ;
        cout << x2 << "\n";
        
    }
}
/*
 
*/